﻿#include "vk_mem_alloc.h"
#include "dmm.h"

#include <cassert>
#include <vector>
#include <algorithm>
#include <random>
#include <iostream>
#include <thread>
#include <list>
#include <mutex>
#include <string.h>
#include <chrono>
#include <numeric>
#include <atomic>
#include <condition_variable>
#include <functional>

namespace dmm
{
	extern VmaAllocator g_hAllocator;
	extern VmaVulkanFunctions CPUDeviceFunctions;
}

#define STRINGIZE(x) STRINGIZE2(x)
#define STRINGIZE2(x) #x
#define LINE_STRING STRINGIZE(__LINE__)
#define TEST(expr)  do { if(!(expr)) { \
        assert(0 && #expr); \
        throw std::runtime_error(__FILE__ "(" LINE_STRING "): ( " #expr " ) == false"); \
    } } while(false)

#ifdef __GNUC__
char* strcpy_s(char* dest, size_t len, const char* src)
{
	strncpy(dest, src, len);

	return dest;
}
#endif

using dmm::g_hAllocator;

typedef std::chrono::high_resolution_clock::time_point time_point;
typedef std::chrono::high_resolution_clock::duration duration;

static constexpr VkDeviceSize KILOBYTE = 1024;
static constexpr VkDeviceSize MEGABYTE = 1024 * 1024;

class RandomNumberGenerator
{
public:
	RandomNumberGenerator() : m_Value{ std::random_device()() } {}
	RandomNumberGenerator(uint32_t seed) : m_Value{ seed } { }
	void Seed(uint32_t seed) { m_Value = seed; }
	uint32_t Generate() { return GenerateFast() ^ (GenerateFast() >> 7); }

private:
	uint32_t m_Value;
	uint32_t GenerateFast() { return m_Value = (m_Value * 196314165 + 907633515); }
};

void SaveFile(const char* filePath, const void* data, size_t dataSize)
{
	FILE* f = fopen(filePath, "wb");
	if (f)
	{
		fwrite(data, 1, dataSize, f);
		fclose(f);
	}
	else
		assert(0);
}

void SaveAllocatorStatsToFile(const char* filePath)
{
#if !defined(VMA_STATS_STRING_ENABLED) || VMA_STATS_STRING_ENABLED
	printf("Saving JSON dump to file \"%s\"\n", filePath);
	char* stats;
	vmaBuildStatsString(g_hAllocator, &stats, VK_TRUE);
	SaveFile(filePath, stats, strlen(stats));
	vmaFreeStatsString(g_hAllocator, stats);
#endif
}

struct AllocInfo
{
	VmaAllocation m_Allocation = VK_NULL_HANDLE;
	uint32_t m_StartValue = 0;

	void AllocMemory(
		const VkMemoryRequirements& memReq,
		const VmaAllocationCreateInfo& allocCreateInfo);
	void Destroy();
};

void AllocInfo::AllocMemory(
	const VkMemoryRequirements& memReq,
	const VmaAllocationCreateInfo& allocCreateInfo)
{
	VkResult res = vmaAllocateMemory(g_hAllocator, &memReq, &allocCreateInfo, &m_Allocation, nullptr);
	TEST(res == VK_SUCCESS);
}

void AllocInfo::Destroy()
{
	if (m_Allocation)
	{
		vmaFreeMemory(g_hAllocator, m_Allocation);
		m_Allocation = VK_NULL_HANDLE;
	}
}

inline float ToFloatSeconds(duration d)
{
	return std::chrono::duration_cast<std::chrono::duration<float>>(d).count();
}

static const char* VirtualAlgorithmToStr(uint32_t algorithm)
{
	switch (algorithm)
	{
	case VMA_VIRTUAL_BLOCK_CREATE_LINEAR_ALGORITHM_BIT:
		return "Linear";
	case 0:
		return "TLSF";
	default:
		assert(0);
		return "";
	}
}

static const char* GetVirtualAllocationStrategyName(VmaVirtualAllocationCreateFlags allocStrategy)
{
	switch (allocStrategy)
	{
	case VMA_VIRTUAL_ALLOCATION_CREATE_STRATEGY_MIN_MEMORY_BIT: return "MIN_MEMORY"; break;
	case VMA_VIRTUAL_ALLOCATION_CREATE_STRATEGY_MIN_TIME_BIT: return "MIN_TIME"; break;
	case 0: return "Default"; break;
	default: assert(0); return "";
	}
}

static void TestUserData()
{
	VkResult res;
	VkMemoryRequirements req = {};
	req.size = 0x10000;
	req.memoryTypeBits = UINT32_MAX;

	for (uint32_t testIndex = 0; testIndex < 2; ++testIndex)
	{
		// Opaque pointer
		{

			void* numberAsPointer = (void*)(size_t)0xC2501FF3u;
			void* pointerToSomething = &res;

			VmaAllocationCreateInfo allocCreateInfo = {};
			allocCreateInfo.pUserData = numberAsPointer;
			if (testIndex == 1)
				allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;

			VkBuffer buf; VmaAllocation alloc; VmaAllocationInfo allocInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo);
			TEST(res == VK_SUCCESS);
			TEST(allocInfo.pUserData == numberAsPointer);

			vmaGetAllocationInfo(g_hAllocator, alloc, &allocInfo);
			TEST(allocInfo.pUserData == numberAsPointer);

			vmaSetAllocationUserData(g_hAllocator, alloc, pointerToSomething);
			vmaGetAllocationInfo(g_hAllocator, alloc, &allocInfo);
			TEST(allocInfo.pUserData == pointerToSomething);

			vmaFreeMemory(g_hAllocator, alloc);
		}

		// String
		{
			const char* name1 = "Buffer name \\\"\'<>&% \nSecond line .,;=";
			const char* name2 = "2";
			const size_t name1Len = strlen(name1);

			char* name1Buf = new char[name1Len + 1];
			strcpy_s(name1Buf, name1Len + 1, name1);

			VmaAllocationCreateInfo allocCreateInfo = {};
			allocCreateInfo.flags = VMA_ALLOCATION_CREATE_USER_DATA_COPY_STRING_BIT;
			allocCreateInfo.pUserData = name1Buf;
			if (testIndex == 1)
				allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;

			VkBuffer buf; VmaAllocation alloc; VmaAllocationInfo allocInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo);
			TEST(res == VK_SUCCESS);
			TEST(allocInfo.pName != nullptr && allocInfo.pName != name1Buf);
			TEST(strcmp(name1, allocInfo.pName) == 0);

			delete[] name1Buf;

			vmaGetAllocationInfo(g_hAllocator, alloc, &allocInfo);
			TEST(strcmp(name1, allocInfo.pName) == 0);

			vmaSetAllocationName(g_hAllocator, alloc, name2);
			vmaGetAllocationInfo(g_hAllocator, alloc, &allocInfo);
			TEST(strcmp(name2, allocInfo.pName) == 0);

			vmaSetAllocationName(g_hAllocator, alloc, nullptr);
			vmaGetAllocationInfo(g_hAllocator, alloc, &allocInfo);
			TEST(allocInfo.pName == nullptr);

			vmaFreeMemory(g_hAllocator, alloc);
		}
	}
}

static void TestInvalidAllocations()
{
	VkResult res;

	VmaAllocationCreateInfo allocCreateInfo = {};

	// Try to allocate 0 bytes.
	{
		VkMemoryRequirements memReq = {};
		memReq.size = 0; // !!!
		memReq.alignment = 4;
		memReq.memoryTypeBits = UINT32_MAX;
		VmaAllocation alloc = VK_NULL_HANDLE;
		res = vmaAllocateMemory(g_hAllocator, &memReq, &allocCreateInfo, &alloc, nullptr);
		TEST(res == VK_ERROR_INITIALIZATION_FAILED && alloc == VK_NULL_HANDLE);
	}

	// Try to create buffer with size = 0.
	{
		VkMemoryRequirements req = {};
		VkBuffer buf = VK_NULL_HANDLE;
		VmaAllocation alloc = VK_NULL_HANDLE;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, nullptr);
		TEST(res == VK_ERROR_INITIALIZATION_FAILED && buf == VK_NULL_HANDLE && alloc == VK_NULL_HANDLE);
	}
}

static void TestMemoryRequirements()
{
	VkResult res;
	VkBuffer buf;
	VmaAllocation alloc;
	VmaAllocationInfo allocInfo;

	const VkPhysicalDeviceMemoryProperties* memProps;
	vmaGetMemoryProperties(g_hAllocator, &memProps);

	VkMemoryRequirements req = {};
	req.size = 128;
	req.memoryTypeBits = UINT32_MAX;

	VmaAllocationCreateInfo allocCreateInfo = {};

	// No requirements.
	res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo);
	TEST(res == VK_SUCCESS);
	vmaFreeMemory(g_hAllocator, alloc);

	// Usage = auto + host access.
	allocCreateInfo.flags = VMA_ALLOCATION_CREATE_HOST_ACCESS_RANDOM_BIT;
	allocCreateInfo.requiredFlags = 0;
	allocCreateInfo.preferredFlags = 0;
	allocCreateInfo.memoryTypeBits = UINT32_MAX;

	res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo);
	TEST(res == VK_SUCCESS);
	TEST(memProps->memoryTypes[allocInfo.memoryType].propertyFlags & VK_MEMORY_PROPERTY_HOST_VISIBLE_BIT);
	vmaFreeMemory(g_hAllocator, alloc);

	// Required flags, preferred flags.
	allocCreateInfo.usage = VMA_MEMORY_USAGE_UNKNOWN;
	allocCreateInfo.flags = 0;
	allocCreateInfo.requiredFlags = VK_MEMORY_PROPERTY_HOST_VISIBLE_BIT | VK_MEMORY_PROPERTY_HOST_COHERENT_BIT;
	allocCreateInfo.preferredFlags = VK_MEMORY_PROPERTY_DEVICE_LOCAL_BIT | VK_MEMORY_PROPERTY_HOST_CACHED_BIT;
	allocCreateInfo.memoryTypeBits = 0;

	res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo);
	TEST(res == VK_SUCCESS);
	TEST(memProps->memoryTypes[allocInfo.memoryType].propertyFlags & VK_MEMORY_PROPERTY_HOST_VISIBLE_BIT);
	TEST(memProps->memoryTypes[allocInfo.memoryType].propertyFlags & VK_MEMORY_PROPERTY_HOST_COHERENT_BIT);
	vmaFreeMemory(g_hAllocator, alloc);

	// memoryTypeBits.
	const uint32_t memType = allocInfo.memoryType;
	allocCreateInfo.usage = VMA_MEMORY_USAGE_UNKNOWN;
	allocCreateInfo.flags = 0;
	allocCreateInfo.requiredFlags = 0;
	allocCreateInfo.preferredFlags = 0;
	allocCreateInfo.memoryTypeBits = 1u << memType;

	res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo);
	TEST(res == VK_SUCCESS);
	TEST(allocInfo.memoryType == memType);
	vmaFreeMemory(g_hAllocator, alloc);

}

static void TestGetAllocatorInfo()
{
	printf("Test vnaGetAllocatorInfo\n");

	VmaAllocatorInfo allocInfo = {};
	vmaGetAllocatorInfo(g_hAllocator, &allocInfo);
}

static void TestJson()
{
	printf("Test JSON\n");

	std::vector<VmaPool> pools;
	std::vector<VmaAllocation> allocs;

	VmaAllocationCreateInfo allocCreateInfo = {};

	VkMemoryRequirements memReq{};
	memReq.size = 1024;
	memReq.memoryTypeBits = UINT32_MAX;

	// Select if using custom pool or default
	for (uint8_t poolType = 0; poolType < 2; ++poolType)
	{
		// Select different memoryTypes
		for (uint8_t memType = 0; memType < 2; ++memType)
		{
			switch (memType)
			{
			case 0:
				allocCreateInfo.flags = VMA_ALLOCATION_CREATE_DONT_BIND_BIT;
				break;
			case 1:
				allocCreateInfo.flags = VMA_ALLOCATION_CREATE_DONT_BIND_BIT | VMA_ALLOCATION_CREATE_HOST_ACCESS_RANDOM_BIT;
				break;
			}

			switch (poolType)
			{
			case 0:
				allocCreateInfo.pool = nullptr;
				break;
			case 1:
			{
				VmaPoolCreateInfo poolCreateInfo = {};
				VmaPool pool;
				TEST(vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool) == VK_SUCCESS);

				allocCreateInfo.pool = pool;
				pools.emplace_back(pool);
				break;
			}
			}

			// Select different allocation flags
			for (uint8_t allocFlag = 0; allocFlag < 2; ++allocFlag)
			{
				switch (allocFlag)
				{
				case 1:
					allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;
					break;
				}

				// Select different alloc types (block, buffer, texture, etc.)
				for (uint8_t allocType = 0; allocType < 1; ++allocType)
				{
					// Select different data stored in the allocation
					for (uint8_t data = 0; data < 4; ++data)
					{
						VmaAllocation alloc = nullptr;

						switch (allocType)
						{
						case 0:
						{
							VmaAllocationCreateInfo localCreateInfo = allocCreateInfo;
							switch (memType)
							{
							case 0:
								localCreateInfo.usage = VMA_MEMORY_USAGE_GPU_ONLY;
								break;
							case 1:
								localCreateInfo.usage = VMA_MEMORY_USAGE_CPU_ONLY;
								break;
							}
							TEST(vmaAllocateMemory(g_hAllocator, &memReq, &localCreateInfo, &alloc, nullptr) == VK_SUCCESS);
							break;
						}
						default:
							break;
						}

						switch (data)
						{
						case 1:
							vmaSetAllocationUserData(g_hAllocator, alloc, (void*)16112007);
							break;
						case 2:
							vmaSetAllocationName(g_hAllocator, alloc, "SHEPURD");
							break;
						case 3:
							vmaSetAllocationUserData(g_hAllocator, alloc, (void*)26012010);
							vmaSetAllocationName(g_hAllocator, alloc, "JOKER");
							break;
						}
						allocs.emplace_back(alloc);
					}
				}

			}
		}
	}
	SaveAllocatorStatsToFile("JSON_VULKAN.json");

	for (auto& alloc : allocs)
		vmaFreeMemory(g_hAllocator, alloc);
	for (auto& pool : pools)
		vmaDestroyPool(g_hAllocator, pool);
}

static void TestBasics()
{
	printf("Test basics\n");

	VkResult res;

	TestGetAllocatorInfo();

	TestMemoryRequirements();

	// Allocation that is MAPPED and not necessarily HOST_VISIBLE.
	{
		VkMemoryRequirements req = {};
		req.size = 128;
		req.memoryTypeBits = UINT32_MAX;

		VmaAllocationCreateInfo allocCreateInfo = {};
		allocCreateInfo.flags = VMA_ALLOCATION_CREATE_HOST_ACCESS_SEQUENTIAL_WRITE_BIT | VMA_ALLOCATION_CREATE_MAPPED_BIT;

		VkBuffer buf; VmaAllocation alloc; VmaAllocationInfo allocInfo;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo);
		TEST(res == VK_SUCCESS);

		vmaFreeMemory(g_hAllocator, alloc);

		// Same with DEDICATED_MEMORY.
		allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo);
		TEST(res == VK_SUCCESS);

		vmaFreeMemory(g_hAllocator, alloc);
	}

	TestUserData();

	TestInvalidAllocations();
}

static void TestVirtualBlocks()
{
	printf("Test virtual blocks\n");

	const VkDeviceSize blockSize = 16 * MEGABYTE;
	const VkDeviceSize alignment = 256;
	VkDeviceSize offset;

	// # Create block 16 MB

	VmaVirtualBlockCreateInfo blockCreateInfo = {};
	blockCreateInfo.size = blockSize;
	VmaVirtualBlock block;
	TEST(vmaCreateVirtualBlock(&blockCreateInfo, &block) == VK_SUCCESS && block);

	// # Allocate 8 MB (also fetch offset from the allocation)

	VmaVirtualAllocationCreateInfo allocCreateInfo = {};
	allocCreateInfo.alignment = alignment;
	allocCreateInfo.pUserData = (void*)(uintptr_t)1;
	allocCreateInfo.size = 8 * MEGABYTE;
	VmaVirtualAllocation allocation0 = VK_NULL_HANDLE;
	TEST(vmaVirtualAllocate(block, &allocCreateInfo, &allocation0, &offset) == VK_SUCCESS);
	TEST(allocation0 != VK_NULL_HANDLE);

	// # Validate the allocation

	VmaVirtualAllocationInfo allocInfo0 = {};
	vmaGetVirtualAllocationInfo(block, allocation0, &allocInfo0);
	TEST(allocInfo0.offset < blockSize);
	TEST(allocInfo0.offset == offset);
	TEST(allocInfo0.size == allocCreateInfo.size);
	TEST(allocInfo0.pUserData == allocCreateInfo.pUserData);

	// # Check SetUserData

	vmaSetVirtualAllocationUserData(block, allocation0, (void*)(uintptr_t)2);
	vmaGetVirtualAllocationInfo(block, allocation0, &allocInfo0);
	TEST(allocInfo0.pUserData == (void*)(uintptr_t)2);

	// # Allocate 4 MB (also test passing null as pOffset during allocation)

	allocCreateInfo.size = 4 * MEGABYTE;
	VmaVirtualAllocation allocation1 = VK_NULL_HANDLE;
	TEST(vmaVirtualAllocate(block, &allocCreateInfo, &allocation1, nullptr) == VK_SUCCESS);
	TEST(allocation1 != VK_NULL_HANDLE);
	VmaVirtualAllocationInfo allocInfo1 = {};
	vmaGetVirtualAllocationInfo(block, allocation1, &allocInfo1);
	TEST(allocInfo1.offset < blockSize);
	TEST(allocInfo1.offset + 4 * MEGABYTE <= allocInfo0.offset || allocInfo0.offset + 8 * MEGABYTE <= allocInfo1.offset); // Check if they don't overlap.

	// # Allocate another 8 MB - it should fail

	allocCreateInfo.size = 8 * MEGABYTE;
	VmaVirtualAllocation allocation2 = VK_NULL_HANDLE;
	TEST(vmaVirtualAllocate(block, &allocCreateInfo, &allocation2, &offset) < 0);
	TEST(allocation2 == VK_NULL_HANDLE);
	TEST(offset == UINT64_MAX);

	// # Free the 4 MB block. Now allocation of 8 MB should succeed.

	vmaVirtualFree(block, allocation1);
	TEST(vmaVirtualAllocate(block, &allocCreateInfo, &allocation2, nullptr) == VK_SUCCESS);
	TEST(allocation2 != VK_NULL_HANDLE);
	VmaVirtualAllocationInfo allocInfo2 = {};
	vmaGetVirtualAllocationInfo(block, allocation2, &allocInfo2);
	TEST(allocInfo2.offset < blockSize);
	TEST(allocInfo2.offset + 4 * MEGABYTE <= allocInfo0.offset || allocInfo0.offset + 8 * MEGABYTE <= allocInfo2.offset); // Check if they don't overlap.

	// # Calculate statistics

	VmaDetailedStatistics statInfo = {};
	vmaCalculateVirtualBlockStatistics(block, &statInfo);
	TEST(statInfo.statistics.allocationCount == 2);
	TEST(statInfo.statistics.blockCount == 1);
	TEST(statInfo.statistics.allocationBytes == blockSize);
	TEST(statInfo.statistics.blockBytes == blockSize);

	// # Generate JSON dump

#if !defined(VMA_STATS_STRING_ENABLED) || VMA_STATS_STRING_ENABLED
	char* json = nullptr;
	vmaBuildVirtualBlockStatsString(block, &json, VK_TRUE);
	{
		//result of "printf %p" differs between Windows and Linux
		//TEST(str.find("\"UserData\": \"0000000000000001\"") != std::string::npos);
		//TEST(str.find("\"UserData\": \"0000000000000002\"") != std::string::npos);
	}
	vmaFreeVirtualBlockStatsString(block, json);
#endif

	// # Free alloc0, leave alloc2 unfreed.

	vmaVirtualFree(block, allocation0);

	// # Test free of null allocation.
	vmaVirtualFree(block, VK_NULL_HANDLE);

	// # Test alignment

	{
		constexpr size_t allocCount = 10;
		VmaVirtualAllocation allocations[allocCount] = {};
		for (size_t i = 0; i < allocCount; ++i)
		{
			const bool alignment0 = i == allocCount - 1;
			allocCreateInfo.size = i * 3 + 15;
			allocCreateInfo.alignment = alignment0 ? 0 : 8;
			TEST(vmaVirtualAllocate(block, &allocCreateInfo, &allocations[i], nullptr) == VK_SUCCESS);
			TEST(allocations[i] != VK_NULL_HANDLE);
			if (!alignment0)
			{
				VmaVirtualAllocationInfo info;
				vmaGetVirtualAllocationInfo(block, allocations[i], &info);
				TEST(info.offset % allocCreateInfo.alignment == 0);
			}
		}

		for (size_t i = allocCount; i--; )
		{
			vmaVirtualFree(block, allocations[i]);
		}
	}

	// # Final cleanup

	vmaVirtualFree(block, allocation2);
	vmaDestroyVirtualBlock(block);

	{
		// Another virtual block, using Clear this time.
		TEST(vmaCreateVirtualBlock(&blockCreateInfo, &block) == VK_SUCCESS);

		allocCreateInfo = VmaVirtualAllocationCreateInfo{};
		allocCreateInfo.size = MEGABYTE;

		for (size_t i = 0; i < 8; ++i)
		{
			VmaVirtualAllocation allocation;
			TEST(vmaVirtualAllocate(block, &allocCreateInfo, &allocation, nullptr) == VK_SUCCESS);
		}

		vmaClearVirtualBlock(block);
		vmaDestroyVirtualBlock(block);
	}
}

static void TestVirtualBlocksAlgorithms()
{
	printf("Test virtual blocks algorithms\n");

	RandomNumberGenerator rand{ 3454335 };
	auto calcRandomAllocSize = [&rand]() -> VkDeviceSize { return rand.Generate() % 20 + 5; };

	for (size_t algorithmIndex = 0; algorithmIndex < 2; ++algorithmIndex)
	{
		// Create the block
		VmaVirtualBlockCreateInfo blockCreateInfo = {};
		blockCreateInfo.size = 10'000;
		switch (algorithmIndex)
		{
		case 1: blockCreateInfo.flags = VMA_VIRTUAL_BLOCK_CREATE_LINEAR_ALGORITHM_BIT; break;
		}
		VmaVirtualBlock block = nullptr;
		VkResult res = vmaCreateVirtualBlock(&blockCreateInfo, &block);
		TEST(res == VK_SUCCESS);

		struct AllocData
		{
			VmaVirtualAllocation allocation;
			VkDeviceSize allocOffset, requestedSize, allocationSize;
		};
		std::vector<AllocData> allocations;

		// Make some allocations
		for (size_t i = 0; i < 20; ++i)
		{
			VmaVirtualAllocationCreateInfo allocCreateInfo = {};
			allocCreateInfo.size = calcRandomAllocSize();
			allocCreateInfo.pUserData = (void*)(uintptr_t)(allocCreateInfo.size * 10);
			if (i < 10) {}
			else if (i < 12) allocCreateInfo.flags = VMA_VIRTUAL_ALLOCATION_CREATE_STRATEGY_MIN_MEMORY_BIT;
			else if (i < 14) allocCreateInfo.flags = VMA_VIRTUAL_ALLOCATION_CREATE_STRATEGY_MIN_TIME_BIT;
			else if (i < 16) allocCreateInfo.flags = VMA_VIRTUAL_ALLOCATION_CREATE_STRATEGY_MIN_MEMORY_BIT;
			else if (i < 18 && algorithmIndex == 1) allocCreateInfo.flags = VMA_VIRTUAL_ALLOCATION_CREATE_UPPER_ADDRESS_BIT;

			AllocData alloc = {};
			alloc.requestedSize = allocCreateInfo.size;
			res = vmaVirtualAllocate(block, &allocCreateInfo, &alloc.allocation, nullptr);
			TEST(res == VK_SUCCESS);

			VmaVirtualAllocationInfo allocInfo;
			vmaGetVirtualAllocationInfo(block, alloc.allocation, &allocInfo);
			TEST(allocInfo.size >= allocCreateInfo.size);
			alloc.allocOffset = allocInfo.offset;
			alloc.allocationSize = allocInfo.size;

			allocations.push_back(alloc);
		}

		// Free some of the allocations
		for (size_t i = 0; i < 5; ++i)
		{
			const size_t index = rand.Generate() % allocations.size();
			vmaVirtualFree(block, allocations[index].allocation);
			allocations.erase(allocations.begin() + index);
		}

		// Allocate some more
		for (size_t i = 0; i < 6; ++i)
		{
			VmaVirtualAllocationCreateInfo allocCreateInfo = {};
			allocCreateInfo.size = calcRandomAllocSize();
			allocCreateInfo.pUserData = (void*)(uintptr_t)(allocCreateInfo.size * 10);

			AllocData alloc = {};
			alloc.requestedSize = allocCreateInfo.size;
			res = vmaVirtualAllocate(block, &allocCreateInfo, &alloc.allocation, nullptr);
			TEST(res == VK_SUCCESS);

			VmaVirtualAllocationInfo allocInfo;
			vmaGetVirtualAllocationInfo(block, alloc.allocation, &allocInfo);
			TEST(allocInfo.size >= allocCreateInfo.size);
			alloc.allocOffset = allocInfo.offset;
			alloc.allocationSize = allocInfo.size;

			allocations.push_back(alloc);
		}

		// Allocate some with extra alignment
		for (size_t i = 0; i < 3; ++i)
		{
			VmaVirtualAllocationCreateInfo allocCreateInfo = {};
			allocCreateInfo.size = calcRandomAllocSize();
			allocCreateInfo.alignment = 16;
			allocCreateInfo.pUserData = (void*)(uintptr_t)(allocCreateInfo.size * 10);

			AllocData alloc = {};
			alloc.requestedSize = allocCreateInfo.size;
			res = vmaVirtualAllocate(block, &allocCreateInfo, &alloc.allocation, nullptr);
			TEST(res == VK_SUCCESS);

			VmaVirtualAllocationInfo allocInfo;
			vmaGetVirtualAllocationInfo(block, alloc.allocation, &allocInfo);
			TEST(allocInfo.offset % 16 == 0);
			TEST(allocInfo.size >= allocCreateInfo.size);
			alloc.allocOffset = allocInfo.offset;
			alloc.allocationSize = allocInfo.size;

			allocations.push_back(alloc);
		}

		// Check if the allocations don't overlap
		std::sort(allocations.begin(), allocations.end(), [](const AllocData& lhs, const AllocData& rhs) {
			return lhs.allocOffset < rhs.allocOffset; });
		for (size_t i = 0; i < allocations.size() - 1; ++i)
		{
			TEST(allocations[i + 1].allocOffset >= allocations[i].allocOffset + allocations[i].allocationSize);
		}

		// Check pUserData
		{
			const AllocData& alloc = allocations.back();
			VmaVirtualAllocationInfo allocInfo = {};
			vmaGetVirtualAllocationInfo(block, alloc.allocation, &allocInfo);
			TEST((uintptr_t)allocInfo.pUserData == alloc.requestedSize * 10);

			vmaSetVirtualAllocationUserData(block, alloc.allocation, (void*)(uintptr_t)666);
			vmaGetVirtualAllocationInfo(block, alloc.allocation, &allocInfo);
			TEST((uintptr_t)allocInfo.pUserData == 666);
		}

		// Calculate statistics
		{
			VkDeviceSize actualAllocSizeMin = VK_WHOLE_SIZE, actualAllocSizeMax = 0, actualAllocSizeSum = 0;
			std::for_each(allocations.begin(), allocations.end(), [&](const AllocData& a) {
				actualAllocSizeMin = std::min(actualAllocSizeMin, a.allocationSize);
				actualAllocSizeMax = std::max(actualAllocSizeMax, a.allocationSize);
				actualAllocSizeSum += a.allocationSize;
			});

			VmaDetailedStatistics statInfo = {};
			vmaCalculateVirtualBlockStatistics(block, &statInfo);
			TEST(statInfo.statistics.allocationCount == allocations.size());
			TEST(statInfo.statistics.blockCount == 1);
			TEST(statInfo.statistics.blockBytes == blockCreateInfo.size);
			TEST(statInfo.allocationSizeMax == actualAllocSizeMax);
			TEST(statInfo.allocationSizeMin == actualAllocSizeMin);
			TEST(statInfo.statistics.allocationBytes >= actualAllocSizeSum);
		}

#if !defined(VMA_STATS_STRING_ENABLED) || VMA_STATS_STRING_ENABLED
		// Build JSON dump string
		{
			char* json = nullptr;
			vmaBuildVirtualBlockStatsString(block, &json, VK_TRUE);
			int I = 0; // put a breakpoint here to debug
			vmaFreeVirtualBlockStatsString(block, json);
		}
#endif

		// Final cleanup
		vmaClearVirtualBlock(block);
		vmaDestroyVirtualBlock(block);
	}
}

static void TestAllocationVersusResourceSize()
{
	printf("Test allocation versus resource size\n");

	VkMemoryRequirements req = {0};
	req.size = 22921;
	req.memoryTypeBits = INT32_MAX;

	VmaAllocationCreateInfo allocCreateInfo = {};
	allocCreateInfo.flags = VMA_ALLOCATION_CREATE_HOST_ACCESS_SEQUENTIAL_WRITE_BIT;

	for (uint32_t i = 0; i < 2; ++i)
	{
		if (i == 1)
			allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;
		else
			allocCreateInfo.flags &= ~VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;

		AllocInfo info;
		info.AllocMemory(req, allocCreateInfo);

		VmaAllocationInfo allocInfo = {};
		vmaGetAllocationInfo(g_hAllocator, info.m_Allocation, &allocInfo);
		//printf("  Buffer size = %llu, allocation size = %llu\n", bufCreateInfo.size, allocInfo.size);

		// Map and test accessing entire area of the allocation, not only the buffer.
		void* mappedPtr = nullptr;
		VkResult res = vmaMapMemory(g_hAllocator, info.m_Allocation, &mappedPtr);
		TEST(res == VK_SUCCESS);

		memset(mappedPtr, 0xCC, (size_t)allocInfo.size);

		vmaUnmapMemory(g_hAllocator, info.m_Allocation);

		info.Destroy();
	}
}

static void TestPool_MinBlockCount()
{
#if defined(VMA_DEBUG_MARGIN) && VMA_DEBUG_MARGIN > 0
	return;
#endif

	printf("Test Pool MinBlockCount\n");
	VkResult res;

	static const VkDeviceSize ALLOC_SIZE = 512ull * 1024;
	static const VkDeviceSize BLOCK_SIZE = ALLOC_SIZE * 2; // Each block can fit 2 allocations.

	VmaAllocationCreateInfo allocCreateInfo = {};
	VkMemoryRequirements req = {};
	req.size = ALLOC_SIZE;
	req.memoryTypeBits = UINT32_MAX;

	VmaPoolCreateInfo poolCreateInfo = {};
	poolCreateInfo.blockSize = BLOCK_SIZE;
	poolCreateInfo.minBlockCount = 2; // At least 2 blocks always present.

	VmaPool pool = VK_NULL_HANDLE;
	res = vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool);
	TEST(res == VK_SUCCESS && pool != VK_NULL_HANDLE);

	// Check that there are 2 blocks preallocated as requested.
	VmaDetailedStatistics begPoolStats = {};
	vmaCalculatePoolStatistics(g_hAllocator, pool, &begPoolStats);
	TEST(begPoolStats.statistics.blockCount == 2 &&
		begPoolStats.statistics.allocationCount == 0 &&
		begPoolStats.statistics.blockBytes == BLOCK_SIZE * 2);

	// Allocate 5 buffers to create 3 blocks.
	static const uint32_t BUF_COUNT = 5;
	allocCreateInfo.pool = pool;
	std::vector<AllocInfo> allocs(BUF_COUNT);
	for (uint32_t i = 0; i < BUF_COUNT; ++i)
	{
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &allocs[i].m_Allocation, nullptr);
		TEST(res == VK_SUCCESS  && allocs[i].m_Allocation != VK_NULL_HANDLE);
	}

	// Check that there are really 3 blocks.
	VmaDetailedStatistics poolStats2 = {};
	vmaCalculatePoolStatistics(g_hAllocator, pool, &poolStats2);
	TEST(poolStats2.statistics.blockCount == 3 &&
		poolStats2.statistics.allocationCount == BUF_COUNT &&
		poolStats2.statistics.blockBytes == BLOCK_SIZE * 3);

	// Free two first allocations to make one block empty.
	allocs[0].Destroy();
	allocs[1].Destroy();

	// Check that there are still 3 blocks due to hysteresis.
	VmaDetailedStatistics poolStats3 = {};
	vmaCalculatePoolStatistics(g_hAllocator, pool, &poolStats3);
	TEST(poolStats3.statistics.blockCount == 3 &&
		poolStats3.statistics.allocationCount == BUF_COUNT - 2 &&
		poolStats2.statistics.blockBytes == BLOCK_SIZE * 3);

	// Free the last allocation to make second block empty.
	allocs[BUF_COUNT - 1].Destroy();

	// Check that there are now 2 blocks only.
	VmaDetailedStatistics poolStats4 = {};
	vmaCalculatePoolStatistics(g_hAllocator, pool, &poolStats4);
	TEST(poolStats4.statistics.blockCount == 2 &&
		poolStats4.statistics.allocationCount == BUF_COUNT - 3 &&
		poolStats4.statistics.blockBytes == BLOCK_SIZE * 2);

	// Cleanup.
	for (size_t i = allocs.size(); i--; )
	{
		allocs[i].Destroy();
	}
	vmaDestroyPool(g_hAllocator, pool);
}

static void TestPool_MinAllocationAlignment()
{
	printf("Test Pool MinAllocationAlignment\n");
	VkResult res;

	static const VkDeviceSize ALLOC_SIZE = 32;
	static const VkDeviceSize BLOCK_SIZE = 1024 * 1024;
	static const VkDeviceSize MIN_ALLOCATION_ALIGNMENT = 64 * 1024;

	VmaAllocationCreateInfo allocCreateInfo = {};
	VkMemoryRequirements req = {};
	req.size = ALLOC_SIZE;
	req.memoryTypeBits = UINT32_MAX;

	VmaPoolCreateInfo poolCreateInfo = {};
	poolCreateInfo.blockSize = BLOCK_SIZE;
	poolCreateInfo.minAllocationAlignment = MIN_ALLOCATION_ALIGNMENT;

	VmaPool pool = VK_NULL_HANDLE;
	res = vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool);
	TEST(res == VK_SUCCESS && pool != VK_NULL_HANDLE);

	static const uint32_t BUF_COUNT = 4;
	allocCreateInfo = {};
	allocCreateInfo.pool = pool;
	std::vector<AllocInfo> allocs(BUF_COUNT);
	for (uint32_t i = 0; i < BUF_COUNT; ++i)
	{
		VmaAllocationInfo allocInfo = {};
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &allocs[i].m_Allocation, &allocInfo);
		TEST(res == VK_SUCCESS  && allocs[i].m_Allocation != VK_NULL_HANDLE);
		TEST(allocInfo.offset % MIN_ALLOCATION_ALIGNMENT == 0);
	}

	// Cleanup.
	for (size_t i = allocs.size(); i--; )
	{
		allocs[i].Destroy();
	}
	vmaDestroyPool(g_hAllocator, pool);
}

static void TestPoolsAndAllocationParameters()
{
	printf("Test pools and allocation parameters\n");

	VkMemoryRequirements req = {};
	req.size = 1 * MEGABYTE;
	req.memoryTypeBits = UINT32_MAX;

	VmaAllocationCreateInfo allocCreateInfo = {};
	uint32_t memTypeIndex = 0;

	VmaPool pool1 = nullptr, pool2 = nullptr;
	std::vector<VmaAllocation> vecAllocs;

	uint32_t totalNewAllocCount = 0, totalNewBlockCount = 0;
	VmaTotalStatistics statsBeg, statsEnd;
	vmaCalculateStatistics(g_hAllocator, &statsBeg);

	VkResult res;

	// poolTypeI:
	// 0 = default pool
	// 1 = custom pool, default (flexible) block size and block count
	// 2 = custom pool, fixed block size and limited block count
	for (size_t poolTypeI = 0; poolTypeI < 3; ++poolTypeI)
	{
		if (poolTypeI == 0)
		{
			allocCreateInfo.pool = nullptr;
		}
		else if (poolTypeI == 1)
		{
			VmaPoolCreateInfo poolCreateInfo = {};
			poolCreateInfo.memoryTypeIndex = memTypeIndex;
			res = vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool1);
			TEST(res == VK_SUCCESS);
			allocCreateInfo.pool = pool1;
		}
		else if (poolTypeI == 2)
		{
			VmaPoolCreateInfo poolCreateInfo = {};
			poolCreateInfo.memoryTypeIndex = memTypeIndex;
			poolCreateInfo.maxBlockCount = 1;
			poolCreateInfo.blockSize = 2 * MEGABYTE + MEGABYTE / 2; // 2.5 MB
			res = vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool2);
			TEST(res == VK_SUCCESS);
			allocCreateInfo.pool = pool2;
		}

		uint32_t poolAllocCount = 0, poolBlockCount = 0;
		VmaAllocation alloc = {};
		VmaAllocationInfo allocInfo[4] = {};

		// Default parameters
		allocCreateInfo.flags = 0;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo[0]);
		TEST(res == VK_SUCCESS && alloc);
		vecAllocs.push_back(std::move(alloc));
		++poolAllocCount;

		// DEDICATED. Should not try pool2 as it asserts on invalid call.
		if (poolTypeI != 2)
		{
			allocCreateInfo.flags = VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo[1]);
			TEST(res == VK_SUCCESS && alloc);
			TEST(allocInfo[1].offset == 0); // Dedicated
			TEST(allocInfo[1].deviceMemory != allocInfo[0].deviceMemory); // Dedicated
			vecAllocs.push_back(std::move(alloc));
			++poolAllocCount;
		}

		// NEVER_ALLOCATE #1
		allocCreateInfo.flags = VMA_ALLOCATION_CREATE_NEVER_ALLOCATE_BIT;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo[2]);
		TEST(res == VK_SUCCESS && alloc);
		TEST(allocInfo[2].deviceMemory == allocInfo[0].deviceMemory); // Same memory block as default one.
		TEST(allocInfo[2].offset != allocInfo[0].offset);
		vecAllocs.push_back(std::move(alloc));
		++poolAllocCount;

		// NEVER_ALLOCATE #2. Should fail in pool2 as it has no space.
		allocCreateInfo.flags = VMA_ALLOCATION_CREATE_NEVER_ALLOCATE_BIT;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo[3]);
		if (poolTypeI == 2)
			TEST(res < 0);
		else
		{
			TEST(res == VK_SUCCESS && alloc);
			vecAllocs.push_back(std::move(alloc));
			++poolAllocCount;
		}

		// Pool stats
		switch (poolTypeI)
		{
		case 0: poolBlockCount = 1; break; // At least 1 added for dedicated allocation.
		case 1: poolBlockCount = 2; break; // 1 for custom pool block and 1 for dedicated allocation.
		case 2: poolBlockCount = 1; break; // Only custom pool, no dedicated allocation.
		}

		if (poolTypeI > 0)
		{
			VmaDetailedStatistics poolStats = {};
			vmaCalculatePoolStatistics(g_hAllocator, poolTypeI == 2 ? pool2 : pool1, &poolStats);
			TEST(poolStats.statistics.allocationCount == poolAllocCount);
			const VkDeviceSize usedSize = poolStats.statistics.allocationBytes;
			TEST(usedSize == poolAllocCount * MEGABYTE);
			TEST(poolStats.statistics.blockCount == poolBlockCount);
		}

		totalNewAllocCount += poolAllocCount;
		totalNewBlockCount += poolBlockCount;
	}

	vmaCalculateStatistics(g_hAllocator, &statsEnd);
	TEST(statsEnd.total.statistics.allocationCount == statsBeg.total.statistics.allocationCount + totalNewAllocCount);
	TEST(statsEnd.total.statistics.blockCount >= statsBeg.total.statistics.blockCount + totalNewBlockCount);
	TEST(statsEnd.total.statistics.allocationBytes == statsBeg.total.statistics.allocationBytes + totalNewAllocCount * MEGABYTE);

	for (auto& e : vecAllocs)
		vmaFreeMemory(g_hAllocator, e);

	vmaDestroyPool(g_hAllocator, pool2);
	vmaDestroyPool(g_hAllocator, pool1);
}


void TestHeapSizeLimit()
{
	printf("Test heap size limit\n");

	const VkDeviceSize HEAP_SIZE_LIMIT = 100ull * 1024 * 1024; // 100 MB
	const VkDeviceSize BLOCK_SIZE = 10ull * 1024 * 1024; // 10 MB

	VkDeviceSize heapSizeLimit[VK_MAX_MEMORY_HEAPS];
	for (uint32_t i = 0; i < VK_MAX_MEMORY_HEAPS; ++i)
	{
		heapSizeLimit[i] = HEAP_SIZE_LIMIT;
	}

	VmaAllocatorCreateInfo allocatorCreateInfo = {};
	allocatorCreateInfo.vulkanApiVersion = VK_API_VERSION_1_2;
	allocatorCreateInfo.pVulkanFunctions = &dmm::CPUDeviceFunctions;	//必须提供
	allocatorCreateInfo.pHeapSizeLimit = heapSizeLimit;

	VmaAllocator hAllocator;
	VkResult res = vmaCreateAllocator(&allocatorCreateInfo, &hAllocator);
	TEST(res == VK_SUCCESS);

	struct Item
	{
		VmaAllocation hAlloc;
	};
	std::vector<Item> items;

	VkMemoryRequirements req = {};
	req.memoryTypeBits = UINT32_MAX;

	// 1. Allocate two blocks of dedicated memory, half the size of BLOCK_SIZE.
	VmaAllocationInfo dedicatedAllocInfo;
	{
		VmaAllocationCreateInfo allocCreateInfo = {};
		allocCreateInfo.flags = VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;

		req.size = BLOCK_SIZE / 2;

		for (size_t i = 0; i < 2; ++i)
		{
			Item item;
			res = vmaAllocateMemory(hAllocator, &req, &allocCreateInfo, &item.hAlloc, &dedicatedAllocInfo);
			TEST(res == VK_SUCCESS);
			items.push_back(item);
		}
	}

	// Create pool to make sure allocations must be out of this memory type.
	VmaPoolCreateInfo poolCreateInfo = {};
	poolCreateInfo.memoryTypeIndex = dedicatedAllocInfo.memoryType;
	poolCreateInfo.blockSize = BLOCK_SIZE;

	VmaPool hPool;
	res = vmaCreatePool(hAllocator, &poolCreateInfo, &hPool);
	TEST(res == VK_SUCCESS);

	// 2. Allocate normal buffers from all the remaining memory.
	{
		VmaAllocationCreateInfo allocCreateInfo = {};
		allocCreateInfo.pool = hPool;

		req.size = BLOCK_SIZE / 2;

		const size_t bufCount = ((HEAP_SIZE_LIMIT / BLOCK_SIZE) - 1) * 2;
		for (size_t i = 0; i < bufCount; ++i)
		{
			Item item;
			res = vmaAllocateMemory(hAllocator, &req, &allocCreateInfo, &item.hAlloc, nullptr);
			TEST(res == VK_SUCCESS);
			items.push_back(item);
		}
	}

	// 3. Allocation of one more (even small) buffer should fail.
	{
		VmaAllocationCreateInfo allocCreateInfo = {};
		allocCreateInfo.pool = hPool;

		req.size = 128;

		VmaAllocation hAlloc;
		res = vmaAllocateMemory(hAllocator, &req, &allocCreateInfo, &hAlloc, nullptr);
		TEST(res == VK_ERROR_OUT_OF_DEVICE_MEMORY);
	}

	// Destroy everything.
	for (size_t i = items.size(); i--; )
	{
		vmaFreeMemory(hAllocator, items[i].hAlloc);
	}

	vmaDestroyPool(hAllocator, hPool);

	vmaDestroyAllocator(hAllocator);
}

uint32_t g_FrameIndex = 0;

struct BufferInfo
{
	VmaAllocation Allocation = VK_NULL_HANDLE;
};

static uint32_t MemoryTypeToHeap(uint32_t memoryTypeIndex)
{
	const VkPhysicalDeviceMemoryProperties* props;
	vmaGetMemoryProperties(g_hAllocator, &props);
	return props->memoryTypes[memoryTypeIndex].heapIndex;
}

static void TestBudget()
{
	printf("Testing budget...\n");

	static const VkDeviceSize BUF_SIZE = 10ull * 1024 * 1024;
	static const uint32_t BUF_COUNT = 4;

	const VkPhysicalDeviceMemoryProperties* memProps = {};
	vmaGetMemoryProperties(g_hAllocator, &memProps);

	for (uint32_t testIndex = 0; testIndex < 2; ++testIndex)
	{
		vmaSetCurrentFrameIndex(g_hAllocator, ++g_FrameIndex);

		VmaBudget budgetBeg[VK_MAX_MEMORY_HEAPS] = {};
		vmaGetHeapBudgets(g_hAllocator, budgetBeg);

		for (uint32_t i = 0; i < memProps->memoryHeapCount; ++i)
		{
			TEST(budgetBeg[i].budget > 0);
			TEST(budgetBeg[i].budget <= memProps->memoryHeaps[i].size);
			TEST(budgetBeg[i].statistics.allocationBytes <= budgetBeg[i].statistics.blockBytes);
		}

		VkMemoryRequirements req = {};
		req.size = BUF_SIZE;
		req.memoryTypeBits = UINT32_MAX;

		VmaAllocationCreateInfo allocCreateInfo = {};
		if (testIndex == 0)
		{
			allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;
		}

		// CREATE BUFFERS
		uint32_t heapIndex = 0;
		BufferInfo bufInfos[BUF_COUNT] = {};
		for (uint32_t bufIndex = 0; bufIndex < BUF_COUNT; ++bufIndex)
		{
			VmaAllocationInfo allocInfo;
			VkResult res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&bufInfos[bufIndex].Allocation, &allocInfo);
			TEST(res == VK_SUCCESS);
			if (bufIndex == 0)
			{
				heapIndex = MemoryTypeToHeap(allocInfo.memoryType);
			}
			else
			{
				// All buffers need to fall into the same heap.
				TEST(MemoryTypeToHeap(allocInfo.memoryType) == heapIndex);
			}
		}

		VmaBudget budgetWithBufs[VK_MAX_MEMORY_HEAPS] = {};
		vmaGetHeapBudgets(g_hAllocator, budgetWithBufs);

		// DESTROY BUFFERS
		for (size_t bufIndex = BUF_COUNT; bufIndex--; )
		{
			vmaFreeMemory(g_hAllocator, bufInfos[bufIndex].Allocation);
		}

		VmaBudget budgetEnd[VK_MAX_MEMORY_HEAPS] = {};
		vmaGetHeapBudgets(g_hAllocator, budgetEnd);

		// CHECK
		for (uint32_t i = 0; i < memProps->memoryHeapCount; ++i)
		{
			TEST(budgetEnd[i].statistics.allocationBytes <= budgetEnd[i].statistics.blockBytes);
			if (i == heapIndex)
			{
				TEST(budgetEnd[i].statistics.allocationBytes == budgetBeg[i].statistics.allocationBytes);
				TEST(budgetWithBufs[i].statistics.allocationBytes == budgetBeg[i].statistics.allocationBytes + BUF_SIZE * BUF_COUNT);
				TEST(budgetWithBufs[i].statistics.blockBytes >= budgetEnd[i].statistics.blockBytes);
			}
			else
			{
				TEST(budgetEnd[i].statistics.allocationBytes == budgetEnd[i].statistics.allocationBytes &&
					budgetEnd[i].statistics.allocationBytes == budgetWithBufs[i].statistics.allocationBytes);
				TEST(budgetEnd[i].statistics.blockBytes == budgetEnd[i].statistics.blockBytes &&
					budgetEnd[i].statistics.blockBytes == budgetWithBufs[i].statistics.blockBytes);
			}
		}
	}
}

static inline bool MemoryRegionsOverlap(char* ptr1, size_t size1, char* ptr2, size_t size2)
{
	if (ptr1 < ptr2)
		return ptr1 + size1 > ptr2;
	else if (ptr2 < ptr1)
		return ptr2 + size2 > ptr1;
	else
		return true;
}
static void TestMapping()
{
	printf("Testing mapping...\n");

	VkResult res;
	uint32_t memTypeIndex = UINT32_MAX;

	enum TEST
	{
		TEST_NORMAL,
		TEST_POOL,
		TEST_DEDICATED,
		TEST_COUNT
	};
	for (uint32_t testIndex = 0; testIndex < TEST_COUNT; ++testIndex)
	{
		VmaPool pool = nullptr;
		if (testIndex == TEST_POOL)
		{
			TEST(memTypeIndex != UINT32_MAX);
			VmaPoolCreateInfo poolInfo = {};
			poolInfo.memoryTypeIndex = memTypeIndex;
			res = vmaCreatePool(g_hAllocator, &poolInfo, &pool);
			TEST(res == VK_SUCCESS);
		}

		VkMemoryRequirements req = {};
		req.size = 0x10000;
		req.memoryTypeBits = UINT32_MAX;

		VmaAllocationCreateInfo allocCreateInfo = {};
		allocCreateInfo.flags = VMA_ALLOCATION_CREATE_HOST_ACCESS_RANDOM_BIT;
		allocCreateInfo.pool = pool;
		if (testIndex == TEST_DEDICATED)
			allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;

		VmaAllocationInfo allocInfo;

		// Mapped manually

		// Create 2 buffers.
		BufferInfo bufferInfos[3];
		for (size_t i = 0; i < 2; ++i)
		{
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&bufferInfos[i].Allocation, &allocInfo);
			TEST(res == VK_SUCCESS);
			TEST(allocInfo.pMappedData == nullptr);
			memTypeIndex = allocInfo.memoryType;
		}

		// Map buffer 0.
		char* data00 = nullptr;
		res = vmaMapMemory(g_hAllocator, bufferInfos[0].Allocation, (void**)&data00);
		TEST(res == VK_SUCCESS && data00 != nullptr);
		data00[0xFFFF] = data00[0];

		// Map buffer 0 second time.
		char* data01 = nullptr;
		res = vmaMapMemory(g_hAllocator, bufferInfos[0].Allocation, (void**)&data01);
		TEST(res == VK_SUCCESS && data01 == data00);

		// Map buffer 1.
		char* data1 = nullptr;
		res = vmaMapMemory(g_hAllocator, bufferInfos[1].Allocation, (void**)&data1);
		TEST(res == VK_SUCCESS && data1 != nullptr);
		TEST(!MemoryRegionsOverlap(data00, (size_t)req.size, data1, (size_t)req.size));
		data1[0xFFFF] = data1[0];

		// Unmap buffer 0 two times.
		vmaUnmapMemory(g_hAllocator, bufferInfos[0].Allocation);
		vmaUnmapMemory(g_hAllocator, bufferInfos[0].Allocation);
		vmaGetAllocationInfo(g_hAllocator, bufferInfos[0].Allocation, &allocInfo);
		TEST(allocInfo.pMappedData == nullptr);

		// Unmap buffer 1.
		vmaUnmapMemory(g_hAllocator, bufferInfos[1].Allocation);
		vmaGetAllocationInfo(g_hAllocator, bufferInfos[1].Allocation, &allocInfo);
		TEST(allocInfo.pMappedData == nullptr);

		// Create 3rd buffer - persistently mapped.
		allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_MAPPED_BIT;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
			&bufferInfos[2].Allocation, &allocInfo);
		TEST(res == VK_SUCCESS && allocInfo.pMappedData != nullptr);

		// Map buffer 2.
		char* data2 = nullptr;
		res = vmaMapMemory(g_hAllocator, bufferInfos[2].Allocation, (void**)&data2);
		TEST(res == VK_SUCCESS && data2 == allocInfo.pMappedData);
		data2[0xFFFF] = data2[0];

		// Unmap buffer 2.
		vmaUnmapMemory(g_hAllocator, bufferInfos[2].Allocation);
		vmaGetAllocationInfo(g_hAllocator, bufferInfos[2].Allocation, &allocInfo);
		TEST(allocInfo.pMappedData == data2);

		// Destroy all buffers.
		for (size_t i = 3; i--; )
			vmaFreeMemory(g_hAllocator, bufferInfos[i].Allocation);

		vmaDestroyPool(g_hAllocator, pool);
	}
}

static void TestMappingHysteresis()
{
	/*
	We have no way to check here if hysteresis worked as expected,
	but at least we provoke some cases and make sure it doesn't crash or assert.
	You can always check details with the debugger.
	*/

	printf("Test mapping hysteresis\n");

	VkMemoryRequirements req = {};
	req.size = 0x10000;
	req.memoryTypeBits = UINT32_MAX;

	VmaAllocationCreateInfo templateAllocCreateInfo = {};
	templateAllocCreateInfo.flags = VMA_ALLOCATION_CREATE_HOST_ACCESS_SEQUENTIAL_WRITE_BIT;

	VmaPoolCreateInfo poolCreateInfo = {};
	poolCreateInfo.blockSize = 10 * MEGABYTE;
	poolCreateInfo.minBlockCount = poolCreateInfo.maxBlockCount = 1;

	constexpr uint32_t BUF_COUNT = 30;
	bool endOfScenarios = false;
	for (uint32_t scenarioIndex = 0; !endOfScenarios; ++scenarioIndex)
	{
		VmaPool pool;
		TEST(vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool) == VK_SUCCESS);

		BufferInfo buf;
		VmaAllocationInfo allocInfo;

		std::vector<BufferInfo> bufs;

		// Scenario: Create + destroy buffers without mapping. Hysteresis should not launch.
		if (scenarioIndex == 0)
		{
			VmaAllocationCreateInfo allocCreateInfo = {};
			allocCreateInfo.pool = pool;

			for (uint32_t bufIndex = 0; bufIndex < BUF_COUNT; ++bufIndex)
			{
				TEST(vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &buf.Allocation, &allocInfo) == VK_SUCCESS);
				TEST(allocInfo.pMappedData == nullptr);
				vmaFreeMemory(g_hAllocator, buf.Allocation);
			}
		}
		// Scenario:
		// - Create one buffer mapped that stays there.
		// - Create + destroy mapped buffers back and forth. Hysteresis should launch.
		else if (scenarioIndex == 1)
		{
			VmaAllocationCreateInfo allocCreateInfo = {};
			allocCreateInfo.pool = pool;
			allocCreateInfo.flags = VMA_ALLOCATION_CREATE_MAPPED_BIT;

			TEST(vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &buf.Allocation, &allocInfo) == VK_SUCCESS);
			TEST(allocInfo.pMappedData != nullptr);
			bufs.push_back(buf);

			for (uint32_t bufIndex = 0; bufIndex < BUF_COUNT; ++bufIndex)
			{
				TEST(vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &buf.Allocation, &allocInfo) == VK_SUCCESS);
				TEST(allocInfo.pMappedData != nullptr);
				vmaFreeMemory(g_hAllocator, buf.Allocation);
			}
		}
		// Scenario: Create + destroy mapped buffers.
		// Hysteresis should launch as it maps and unmaps back and forth.
		else if (scenarioIndex == 2)
		{
			VmaAllocationCreateInfo allocCreateInfo = {};
			allocCreateInfo.pool = pool;
			allocCreateInfo.flags = VMA_ALLOCATION_CREATE_MAPPED_BIT;

			for (uint32_t bufIndex = 0; bufIndex < BUF_COUNT; ++bufIndex)
			{
				TEST(vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &buf.Allocation, &allocInfo) == VK_SUCCESS);
				TEST(allocInfo.pMappedData != nullptr);
				vmaFreeMemory(g_hAllocator, buf.Allocation);
			}
		}
		// Scenario: Create one buffer and map it back and forth. Hysteresis should launch.
		else if (scenarioIndex == 3)
		{
			VmaAllocationCreateInfo allocCreateInfo = {};
			allocCreateInfo.pool = pool;

			TEST(vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &buf.Allocation, &allocInfo) == VK_SUCCESS);

			for (uint32_t i = 0; i < BUF_COUNT; ++i)
			{
				void* mappedData = nullptr;
				TEST(vmaMapMemory(g_hAllocator, buf.Allocation, &mappedData) == VK_SUCCESS);
				TEST(mappedData != nullptr);
				vmaUnmapMemory(g_hAllocator, buf.Allocation);
			}

			vmaFreeMemory(g_hAllocator, buf.Allocation);
		}
		// Scenario:
		// - Create many buffers
		// - Map + unmap one of them many times. Hysteresis should launch.
		// - Hysteresis should unmap during freeing the buffers.
		else if (scenarioIndex == 4)
		{
			VmaAllocationCreateInfo allocCreateInfo = {};
			allocCreateInfo.pool = pool;

			for (uint32_t bufIndex = 0; bufIndex < BUF_COUNT; ++bufIndex)
			{
				TEST(vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &buf.Allocation, &allocInfo) == VK_SUCCESS);
				TEST(allocInfo.pMappedData == nullptr);
				bufs.push_back(buf);
			}

			for (uint32_t i = 0; i < BUF_COUNT; ++i)
			{
				void* mappedData = nullptr;
				TEST(vmaMapMemory(g_hAllocator, buf.Allocation, &mappedData) == VK_SUCCESS);
				TEST(mappedData != nullptr);
				vmaUnmapMemory(g_hAllocator, buf.Allocation);
			}
		}
		else
			endOfScenarios = true;

		for (size_t i = bufs.size(); i--; )
			vmaFreeMemory(g_hAllocator, bufs[i].Allocation);

		vmaDestroyPool(g_hAllocator, pool);
	}
}

// Test CREATE_MAPPED with required DEVICE_LOCAL. There was a bug with it.
static void TestDeviceLocalMapped()
{
	printf("Test device local mapped\n");

	VkResult res;

	for (uint32_t testIndex = 0; testIndex < 2; ++testIndex)
	{
		VkMemoryRequirements req = {};
		req.size = 4096;
		req.memoryTypeBits = UINT32_MAX;

		VmaPool pool = VK_NULL_HANDLE;
		VmaAllocationCreateInfo allocCreateInfo = {};
		allocCreateInfo.requiredFlags = VK_MEMORY_PROPERTY_DEVICE_LOCAL_BIT;
		allocCreateInfo.flags = VMA_ALLOCATION_CREATE_MAPPED_BIT;
		if (testIndex == 1)
		{
			VmaPoolCreateInfo poolCreateInfo = {};
			res = vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool);
			TEST(res == VK_SUCCESS);
			allocCreateInfo.pool = pool;
		}

		VmaAllocation alloc = VK_NULL_HANDLE;
		VmaAllocationInfo allocInfo = {};
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, &allocInfo);
		TEST(res == VK_SUCCESS && alloc);

		VkMemoryPropertyFlags memTypeFlags = 0;
		vmaGetMemoryTypeProperties(g_hAllocator, allocInfo.memoryType, &memTypeFlags);
		const bool shouldBeMapped = (memTypeFlags & VK_MEMORY_PROPERTY_HOST_VISIBLE_BIT) != 0;
		TEST((allocInfo.pMappedData != nullptr) == shouldBeMapped);

		vmaFreeMemory(g_hAllocator, alloc);
		vmaDestroyPool(g_hAllocator, pool);
	}
}

static void TestMappingMultithreaded()
{
	printf("Testing mapping multithreaded...\n");

	static const uint32_t threadCount = 16;
	static const uint32_t bufferCount = 1024;
	static const uint32_t threadBufferCount = bufferCount / threadCount;

	VkResult res;
	volatile uint32_t memTypeIndex = UINT32_MAX;

	enum TEST
	{
		TEST_NORMAL,
		TEST_POOL,
		TEST_DEDICATED,
		TEST_COUNT
	};
	for (uint32_t testIndex = 0; testIndex < TEST_COUNT; ++testIndex)
	{
		VmaPool pool = nullptr;
		if (testIndex == TEST_POOL)
		{
			TEST(memTypeIndex != UINT32_MAX);
			VmaPoolCreateInfo poolInfo = {};
			poolInfo.memoryTypeIndex = memTypeIndex;
			res = vmaCreatePool(g_hAllocator, &poolInfo, &pool);
			TEST(res == VK_SUCCESS);
		}

		VkMemoryRequirements req = {};
		req.size = 0x10000;
		req.memoryTypeBits = UINT32_MAX;

		VmaAllocationCreateInfo allocCreateInfo = {};
		allocCreateInfo.flags = VMA_ALLOCATION_CREATE_HOST_ACCESS_RANDOM_BIT;
		allocCreateInfo.pool = pool;
		if (testIndex == TEST_DEDICATED)
			allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;

		std::thread threads[threadCount];
		for (uint32_t threadIndex = 0; threadIndex < threadCount; ++threadIndex)
		{
			threads[threadIndex] = std::thread([=, &memTypeIndex]() {
				// ======== THREAD FUNCTION ========

				RandomNumberGenerator rand{ threadIndex };

				enum class MODE
				{
					// Don't map this buffer at all.
					DONT_MAP,
					// Map and quickly unmap.
					MAP_FOR_MOMENT,
					// Map and unmap before destruction.
					MAP_FOR_LONGER,
					// Map two times. Quickly unmap, second unmap before destruction.
					MAP_TWO_TIMES,
					// Create this buffer as persistently mapped.
					PERSISTENTLY_MAPPED,
					COUNT
				};
				std::vector<BufferInfo> bufInfos{ threadBufferCount };
				std::vector<MODE> bufModes{ threadBufferCount };

				for (uint32_t bufferIndex = 0; bufferIndex < threadBufferCount; ++bufferIndex)
				{
					BufferInfo& bufInfo = bufInfos[bufferIndex];
					const MODE mode = (MODE)(rand.Generate() % (uint32_t)MODE::COUNT);
					bufModes[bufferIndex] = mode;

					VmaAllocationCreateInfo localAllocCreateInfo = allocCreateInfo;
					if (mode == MODE::PERSISTENTLY_MAPPED)
						localAllocCreateInfo.flags |= VMA_ALLOCATION_CREATE_MAPPED_BIT;

					VmaAllocationInfo allocInfo;
					VkResult res = vmaAllocateMemory(g_hAllocator, &req, &localAllocCreateInfo,
						&bufInfo.Allocation, &allocInfo);
					TEST(res == VK_SUCCESS);

					if (memTypeIndex == UINT32_MAX)
						memTypeIndex = allocInfo.memoryType;

					char* data = nullptr;

					if (mode == MODE::PERSISTENTLY_MAPPED)
					{
						data = (char*)allocInfo.pMappedData;
						TEST(data != nullptr);
					}
					else if (mode == MODE::MAP_FOR_MOMENT || mode == MODE::MAP_FOR_LONGER ||
						mode == MODE::MAP_TWO_TIMES)
					{
						TEST(data == nullptr);
						res = vmaMapMemory(g_hAllocator, bufInfo.Allocation, (void**)&data);
						TEST(res == VK_SUCCESS && data != nullptr);

						if (mode == MODE::MAP_TWO_TIMES)
						{
							char* data2 = nullptr;
							res = vmaMapMemory(g_hAllocator, bufInfo.Allocation, (void**)&data2);
							TEST(res == VK_SUCCESS && data2 == data);
						}
					}
					else if (mode == MODE::DONT_MAP)
					{
						TEST(allocInfo.pMappedData == nullptr);
					}
					else
						TEST(0);

					// Test if reading and writing from the beginning and end of mapped memory doesn't crash.
					if (data)
						data[0xFFFF] = data[0];

					if (mode == MODE::MAP_FOR_MOMENT || mode == MODE::MAP_TWO_TIMES)
					{
						vmaUnmapMemory(g_hAllocator, bufInfo.Allocation);

						VmaAllocationInfo allocInfo;
						vmaGetAllocationInfo(g_hAllocator, bufInfo.Allocation, &allocInfo);
						if (mode == MODE::MAP_FOR_MOMENT)
							TEST(allocInfo.pMappedData == nullptr);
						else
							TEST(allocInfo.pMappedData == data);
					}

					switch (rand.Generate() % 3)
					{
					case 0: std::this_thread::yield(); break; // Yield.
					case 1: std::this_thread::sleep_for(std::chrono::milliseconds(10)); break; // 10 ms
					// default: No sleep.
					}

					// Test if reading and writing from the beginning and end of mapped memory doesn't crash.
					if (data)
						data[0xFFFF] = data[0];
				}

				for (size_t bufferIndex = threadBufferCount; bufferIndex--; )
				{
					if (bufModes[bufferIndex] == MODE::MAP_FOR_LONGER ||
						bufModes[bufferIndex] == MODE::MAP_TWO_TIMES)
					{
						vmaUnmapMemory(g_hAllocator, bufInfos[bufferIndex].Allocation);

						VmaAllocationInfo allocInfo;
						vmaGetAllocationInfo(g_hAllocator, bufInfos[bufferIndex].Allocation, &allocInfo);
						TEST(allocInfo.pMappedData == nullptr);
					}

					vmaFreeMemory(g_hAllocator, bufInfos[bufferIndex].Allocation);
				}
			});
		}

		for (uint32_t threadIndex = 0; threadIndex < threadCount; ++threadIndex)
			threads[threadIndex].join();

		vmaDestroyPool(g_hAllocator, pool);
	}
}

template <typename T>
static inline T align_up(T val, T align)
{
	return (val + align - 1) / align * align;
}

static void TestLinearAllocator()
{
	printf("Test linear allocator\n");

	RandomNumberGenerator rand{ 645332 };

	VkMemoryRequirements req = {};
	req.size = 1024; // Whatever.
	req.memoryTypeBits = UINT32_MAX;

	VmaPoolCreateInfo poolCreateInfo = {};
	poolCreateInfo.blockSize = 1024 * 300;
	poolCreateInfo.flags = VMA_POOL_CREATE_LINEAR_ALGORITHM_BIT;
	poolCreateInfo.minBlockCount = poolCreateInfo.maxBlockCount = 1;

	VmaPool pool = nullptr;
	VkResult res = vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool);
	TEST(res == VK_SUCCESS);

	VmaAllocationCreateInfo allocCreateInfo = {};
	allocCreateInfo.pool = pool;

	constexpr size_t maxBufCount = 100;
	std::vector<BufferInfo> bufInfo;

	constexpr VkDeviceSize bufSizeMin = 64;
	constexpr VkDeviceSize bufSizeMax = 1024;
	VmaAllocationInfo allocInfo;
	VkDeviceSize prevOffset = 0;

	// Test one-time free.
	for (size_t i = 0; i < 2; ++i)
	{
		// Allocate number of buffers of varying size that surely fit into this block.
		VkDeviceSize bufSumSize = 0;
		for (size_t i = 0; i < maxBufCount; ++i)
		{
			req.size = align_up<VkDeviceSize>(bufSizeMin + rand.Generate() % (bufSizeMax - bufSizeMin), 64);
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			TEST(res == VK_SUCCESS);
			TEST(i == 0 || allocInfo.offset > prevOffset);
			bufInfo.push_back(newBufInfo);
			prevOffset = allocInfo.offset;
			bufSumSize += req.size;
		}

		// Validate pool stats.
		VmaDetailedStatistics stats;
		vmaCalculatePoolStatistics(g_hAllocator, pool, &stats);
		TEST(stats.statistics.blockBytes == poolCreateInfo.blockSize);
		TEST(stats.statistics.blockBytes - stats.statistics.allocationBytes == poolCreateInfo.blockSize - bufSumSize);
		TEST(stats.statistics.allocationCount == bufInfo.size());

		// Destroy the buffers in random order.
		while (!bufInfo.empty())
		{
			const size_t indexToDestroy = rand.Generate() % bufInfo.size();
			const BufferInfo& currBufInfo = bufInfo[indexToDestroy];
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.erase(bufInfo.begin() + indexToDestroy);
		}
	}

	// Test stack.
	{
		// Allocate number of buffers of varying size that surely fit into this block.
		for (size_t i = 0; i < maxBufCount; ++i)
		{
			req.size = align_up<VkDeviceSize>(bufSizeMin + rand.Generate() % (bufSizeMax - bufSizeMin), 64);
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			TEST(res == VK_SUCCESS);
			TEST(i == 0 || allocInfo.offset > prevOffset);
			bufInfo.push_back(newBufInfo);
			prevOffset = allocInfo.offset;
		}

		// Destroy few buffers from top of the stack.
		for (size_t i = 0; i < maxBufCount / 5; ++i)
		{
			const BufferInfo& currBufInfo = bufInfo.back();
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.pop_back();
		}

		// Create some more
		for (size_t i = 0; i < maxBufCount / 5; ++i)
		{
			req.size = align_up<VkDeviceSize>(bufSizeMin + rand.Generate() % (bufSizeMax - bufSizeMin), 64);
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			TEST(res == VK_SUCCESS);
			TEST(i == 0 || allocInfo.offset > prevOffset);
			bufInfo.push_back(newBufInfo);
			prevOffset = allocInfo.offset;
		}

		// Destroy the buffers in reverse order.
		while (!bufInfo.empty())
		{
			const BufferInfo& currBufInfo = bufInfo.back();
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.pop_back();
		}
	}

	// Test ring buffer.
	{
		// Allocate number of buffers that surely fit into this block.
		req.size = bufSizeMax;
		for (size_t i = 0; i < maxBufCount; ++i)
		{
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			TEST(res == VK_SUCCESS);
			TEST(i == 0 || allocInfo.offset > prevOffset);
			bufInfo.push_back(newBufInfo);
			prevOffset = allocInfo.offset;
		}

		// Free and allocate new buffers so many times that we make sure we wrap-around at least once.
		const size_t buffersPerIter = maxBufCount / 10 - 1;
		const size_t iterCount = poolCreateInfo.blockSize / req.size / buffersPerIter * 2;
		for (size_t iter = 0; iter < iterCount; ++iter)
		{
			for (size_t bufPerIter = 0; bufPerIter < buffersPerIter; ++bufPerIter)
			{
				const BufferInfo& currBufInfo = bufInfo.front();
				vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
				bufInfo.erase(bufInfo.begin());
			}
			for (size_t bufPerIter = 0; bufPerIter < buffersPerIter; ++bufPerIter)
			{
				BufferInfo newBufInfo;
				res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
					&newBufInfo.Allocation, &allocInfo);
				TEST(res == VK_SUCCESS);
				bufInfo.push_back(newBufInfo);
			}
		}

		// Allocate buffers until we reach out-of-memory.
		uint32_t debugIndex = 0;
		while (res == VK_SUCCESS)
		{
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			if (res == VK_SUCCESS)
			{
				bufInfo.push_back(newBufInfo);
			}
			else
			{
				TEST(res == VK_ERROR_OUT_OF_DEVICE_MEMORY);
			}
			++debugIndex;
		}

		// Destroy the buffers in random order.
		while (!bufInfo.empty())
		{
			const size_t indexToDestroy = rand.Generate() % bufInfo.size();
			const BufferInfo& currBufInfo = bufInfo[indexToDestroy];
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.erase(bufInfo.begin() + indexToDestroy);
		}
	}

	// Test double stack.
	{
		// Allocate number of buffers of varying size that surely fit into this block, alternate from bottom/top.
		VkDeviceSize prevOffsetLower = 0;
		VkDeviceSize prevOffsetUpper = poolCreateInfo.blockSize;
		for (size_t i = 0; i < maxBufCount; ++i)
		{
			const bool upperAddress = (i % 2) != 0;
			if (upperAddress)
				allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_UPPER_ADDRESS_BIT;
			else
				allocCreateInfo.flags &= ~VMA_ALLOCATION_CREATE_UPPER_ADDRESS_BIT;
			req.size = align_up<VkDeviceSize>(bufSizeMin + rand.Generate() % (bufSizeMax - bufSizeMin), 64);
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			TEST(res == VK_SUCCESS);
			if (upperAddress)
			{
				TEST(allocInfo.offset < prevOffsetUpper);
				prevOffsetUpper = allocInfo.offset;
			}
			else
			{
				TEST(allocInfo.offset >= prevOffsetLower);
				prevOffsetLower = allocInfo.offset;
			}
			TEST(prevOffsetLower < prevOffsetUpper);
			bufInfo.push_back(newBufInfo);
		}

		// Destroy few buffers from top of the stack.
		for (size_t i = 0; i < maxBufCount / 5; ++i)
		{
			const BufferInfo& currBufInfo = bufInfo.back();
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.pop_back();
		}

		// Create some more
		for (size_t i = 0; i < maxBufCount / 5; ++i)
		{
			const bool upperAddress = (i % 2) != 0;
			if (upperAddress)
				allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_UPPER_ADDRESS_BIT;
			else
				allocCreateInfo.flags &= ~VMA_ALLOCATION_CREATE_UPPER_ADDRESS_BIT;
			req.size = align_up<VkDeviceSize>(bufSizeMin + rand.Generate() % (bufSizeMax - bufSizeMin), 64);
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			TEST(res == VK_SUCCESS);
			bufInfo.push_back(newBufInfo);
		}

		// Destroy the buffers in reverse order.
		while (!bufInfo.empty())
		{
			const BufferInfo& currBufInfo = bufInfo.back();
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.pop_back();
		}

		// Create buffers on both sides until we reach out of memory.
		prevOffsetLower = 0;
		prevOffsetUpper = poolCreateInfo.blockSize;
		res = VK_SUCCESS;
		for (size_t i = 0; res == VK_SUCCESS; ++i)
		{
			const bool upperAddress = (i % 2) != 0;
			if (upperAddress)
				allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_UPPER_ADDRESS_BIT;
			else
				allocCreateInfo.flags &= ~VMA_ALLOCATION_CREATE_UPPER_ADDRESS_BIT;
			req.size = align_up<VkDeviceSize>(bufSizeMin + rand.Generate() % (bufSizeMax - bufSizeMin), 64);
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			if (res == VK_SUCCESS)
			{
				if (upperAddress)
				{
					TEST(allocInfo.offset < prevOffsetUpper);
					prevOffsetUpper = allocInfo.offset;
				}
				else
				{
					TEST(allocInfo.offset >= prevOffsetLower);
					prevOffsetLower = allocInfo.offset;
				}
				TEST(prevOffsetLower < prevOffsetUpper);
				bufInfo.push_back(newBufInfo);
			}
		}

		// Destroy the buffers in random order.
		while (!bufInfo.empty())
		{
			const size_t indexToDestroy = rand.Generate() % bufInfo.size();
			const BufferInfo& currBufInfo = bufInfo[indexToDestroy];
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.erase(bufInfo.begin() + indexToDestroy);
		}

		// Create buffers on upper side only, constant size, until we reach out of memory.
		prevOffsetUpper = poolCreateInfo.blockSize;
		res = VK_SUCCESS;
		allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_UPPER_ADDRESS_BIT;
		req.size = bufSizeMax;
		for (size_t i = 0; res == VK_SUCCESS; ++i)
		{
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			if (res == VK_SUCCESS)
			{
				TEST(allocInfo.offset < prevOffsetUpper);
				prevOffsetUpper = allocInfo.offset;
				bufInfo.push_back(newBufInfo);
			}
		}

		// Destroy the buffers in reverse order.
		while (!bufInfo.empty())
		{
			const BufferInfo& currBufInfo = bufInfo.back();
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.pop_back();
		}
	}

	vmaDestroyPool(g_hAllocator, pool);
}

static void ManuallyTestLinearAllocator()
{
	VmaTotalStatistics origStats;
	vmaCalculateStatistics(g_hAllocator, &origStats);

	printf("Manually test linear allocator\n");

	RandomNumberGenerator rand{ 645332 };

	VkMemoryRequirements req = {};
	req.size = 1024; // Whatever.
	req.memoryTypeBits = UINT32_MAX;

	VmaPoolCreateInfo poolCreateInfo = {};
	poolCreateInfo.blockSize = 10 * 1024;
	poolCreateInfo.flags = VMA_POOL_CREATE_LINEAR_ALGORITHM_BIT;
	poolCreateInfo.minBlockCount = poolCreateInfo.maxBlockCount = 1;

	VmaPool pool = nullptr;
	VkResult res = vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool);
	TEST(res == VK_SUCCESS);

	VmaAllocationCreateInfo allocCreateInfo = {};
	allocCreateInfo.pool = pool;

	std::vector<BufferInfo> bufInfo;
	VmaAllocationInfo allocInfo;
	BufferInfo newBufInfo;

	// Test double stack.
	{
		/*
		Lower: Buffer 32 B, Buffer 1024 B, Buffer 32 B
		Upper: Buffer 16 B, Buffer 1024 B, Buffer 128 B

		Totally:
		1 block allocated
		10240 Vulkan bytes
		6 new allocations
		2256 bytes in allocations
		*/

		req.size = 32;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
			&newBufInfo.Allocation, &allocInfo);
		TEST(res == VK_SUCCESS);
		bufInfo.push_back(newBufInfo);

		req.size = 1024;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
			&newBufInfo.Allocation, &allocInfo);
		TEST(res == VK_SUCCESS);
		bufInfo.push_back(newBufInfo);

		req.size = 32;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
			&newBufInfo.Allocation, &allocInfo);
		TEST(res == VK_SUCCESS);
		bufInfo.push_back(newBufInfo);

		allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_UPPER_ADDRESS_BIT;

		req.size = 128;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
			&newBufInfo.Allocation, &allocInfo);
		TEST(res == VK_SUCCESS);
		bufInfo.push_back(newBufInfo);

		req.size = 1024;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
			&newBufInfo.Allocation, &allocInfo);
		TEST(res == VK_SUCCESS);
		bufInfo.push_back(newBufInfo);

		req.size = 16;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
			&newBufInfo.Allocation, &allocInfo);
		TEST(res == VK_SUCCESS);
		bufInfo.push_back(newBufInfo);

		VmaTotalStatistics currStats;
		vmaCalculateStatistics(g_hAllocator, &currStats);
		VmaDetailedStatistics poolStats;
		vmaCalculatePoolStatistics(g_hAllocator, pool, &poolStats);

#if !defined(VMA_STATS_STRING_ENABLED) || VMA_STATS_STRING_ENABLED
		char* statsStr = nullptr;
		vmaBuildStatsString(g_hAllocator, &statsStr, VK_TRUE);

		// PUT BREAKPOINT HERE TO CHECK.
		// Inspect: currStats versus origStats, poolStats, statsStr.
		int I = 0;

		vmaFreeStatsString(g_hAllocator, statsStr);
#endif

		// Destroy the buffers in reverse order.
		while (!bufInfo.empty())
		{
			const BufferInfo& currBufInfo = bufInfo.back();
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.pop_back();
		}
	}

	vmaDestroyPool(g_hAllocator, pool);
}

static void TestLinearAllocatorMultiBlock()
{
	printf("Test linear allocator multi block\n");

	RandomNumberGenerator rand{ 345673 };

	VkMemoryRequirements req = {};
	req.size = 1024 * 1024;
	req.memoryTypeBits = UINT32_MAX;

	VmaPoolCreateInfo poolCreateInfo = {};
	poolCreateInfo.flags = VMA_POOL_CREATE_LINEAR_ALGORITHM_BIT;

	VmaPool pool = nullptr;
	VkResult res = vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool);
	TEST(res == VK_SUCCESS);

	VmaAllocationCreateInfo allocCreateInfo = {};
	allocCreateInfo.pool = pool;

	std::vector<BufferInfo> bufInfo;
	VmaAllocationInfo allocInfo;

	// Test one-time free.
	{
		// Allocate buffers until we move to a second block.
		VkDeviceMemory lastMem = VK_NULL_HANDLE;
		for (uint32_t i = 0; ; ++i)
		{
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			TEST(res == VK_SUCCESS);
			bufInfo.push_back(newBufInfo);
			if (lastMem && allocInfo.deviceMemory != lastMem)
			{
				break;
			}
			lastMem = allocInfo.deviceMemory;
		}

		TEST(bufInfo.size() > 2);

		// Make sure that pool has now two blocks.
		VmaDetailedStatistics poolStats = {};
		vmaCalculatePoolStatistics(g_hAllocator, pool, &poolStats);
		TEST(poolStats.statistics.blockCount == 2);

		// Destroy all the buffers in random order.
		while (!bufInfo.empty())
		{
			const size_t indexToDestroy = rand.Generate() % bufInfo.size();
			const BufferInfo& currBufInfo = bufInfo[indexToDestroy];
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.erase(bufInfo.begin() + indexToDestroy);
		}

		// Make sure that pool has now at most one block.
		vmaCalculatePoolStatistics(g_hAllocator, pool, &poolStats);
		TEST(poolStats.statistics.blockCount <= 1);
	}

	// Test stack.
	{
		// Allocate buffers until we move to a second block.
		VkDeviceMemory lastMem = VK_NULL_HANDLE;
		for (uint32_t i = 0; ; ++i)
		{
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			TEST(res == VK_SUCCESS);
			bufInfo.push_back(newBufInfo);
			if (lastMem && allocInfo.deviceMemory != lastMem)
			{
				break;
			}
			lastMem = allocInfo.deviceMemory;
		}

		TEST(bufInfo.size() > 2);

		// Add few more buffers.
		for (uint32_t i = 0; i < 5; ++i)
		{
			BufferInfo newBufInfo;
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
				&newBufInfo.Allocation, &allocInfo);
			TEST(res == VK_SUCCESS);
			bufInfo.push_back(newBufInfo);
		}

		// Make sure that pool has now two blocks.
		VmaDetailedStatistics poolStats = {};
		vmaCalculatePoolStatistics(g_hAllocator, pool, &poolStats);
		TEST(poolStats.statistics.blockCount == 2);

		// Delete half of buffers, LIFO.
		for (size_t i = 0, countToDelete = bufInfo.size() / 2; i < countToDelete; ++i)
		{
			const BufferInfo& currBufInfo = bufInfo.back();
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.pop_back();
		}

		// Add one more buffer.
		BufferInfo newBufInfo;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
			&newBufInfo.Allocation, &allocInfo);
		TEST(res == VK_SUCCESS);
		bufInfo.push_back(newBufInfo);

		// Make sure that pool has now one block.
		vmaCalculatePoolStatistics(g_hAllocator, pool, &poolStats);
		TEST(poolStats.statistics.blockCount == 1);

		// Delete all the remaining buffers, LIFO.
		while (!bufInfo.empty())
		{
			const BufferInfo& currBufInfo = bufInfo.back();
			vmaFreeMemory(g_hAllocator, currBufInfo.Allocation);
			bufInfo.pop_back();
		}
	}

	vmaDestroyPool(g_hAllocator, pool);
}

static void TestAllocationAlgorithmsCorrectness()
{
	printf("Test allocation algorithm correctness\n");

	constexpr uint32_t LEVEL_COUNT = 12;
	RandomNumberGenerator rand{ 2342435 };

	for (uint32_t isVirtual = 0; isVirtual < 3; ++isVirtual)
	{
		// isVirtual == 0: Use VmaPool, unit is 64 KB.
		// isVirtual == 1: Use VmaVirtualBlock, unit is 64 KB.
		// isVirtual == 2: Use VmaVirtualBlock, unit is 1 B.
		const VkDeviceSize sizeUnit = isVirtual == 2 ? 1 : 0x10000;
		const VkDeviceSize blockSize = (1llu << (LEVEL_COUNT - 1)) * sizeUnit;

		for (uint32_t algorithmIndex = 0; algorithmIndex < 1; ++algorithmIndex)
		{
			VmaPool pool = VK_NULL_HANDLE;
			VmaVirtualBlock virtualBlock = VK_NULL_HANDLE;

			uint32_t algorithm;
			switch (algorithmIndex)
			{
			case 0:
				algorithm = 0;
				break;
			default:
				break;
			}

			if (isVirtual)
			{
				VmaVirtualBlockCreateInfo blockCreateInfo = {};
				blockCreateInfo.flags = algorithm;
				blockCreateInfo.size = blockSize;
				TEST(vmaCreateVirtualBlock(&blockCreateInfo, &virtualBlock) == VK_SUCCESS);
			}
			else
			{
				VmaPoolCreateInfo poolCreateInfo = {};
				poolCreateInfo.blockSize = blockSize;
				poolCreateInfo.flags = algorithm;
				poolCreateInfo.minBlockCount = poolCreateInfo.maxBlockCount = 1;

				VkMemoryRequirements req = {};
				req.size = 0x10000; // Doesn't matter.
				req.memoryTypeBits = UINT32_MAX;
				VmaAllocationCreateInfo allocCreateInfo = {};
				TEST(vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool) == VK_SUCCESS);
			}

			for (uint32_t strategyIndex = 0; strategyIndex < 3; ++strategyIndex)
			{
				struct AllocData
				{
					VmaAllocation alloc = VK_NULL_HANDLE;
					VkBuffer buf = VK_NULL_HANDLE;
					VmaVirtualAllocation virtualAlloc = VK_NULL_HANDLE;
				};
				std::vector<AllocData> allocationsPerLevel[LEVEL_COUNT];

				auto createAllocation = [&](uint32_t level) -> void
				{
					AllocData allocData;
					const VkDeviceSize allocSize = (1llu << level) * sizeUnit;
					if (isVirtual)
					{
						VmaVirtualAllocationCreateInfo allocCreateInfo = {};
						allocCreateInfo.size = allocSize;
						switch (strategyIndex)
						{
						case 1: allocCreateInfo.flags = VMA_VIRTUAL_ALLOCATION_CREATE_STRATEGY_MIN_TIME_BIT; break;
						case 2: allocCreateInfo.flags = VMA_VIRTUAL_ALLOCATION_CREATE_STRATEGY_MIN_MEMORY_BIT; break;
						}
						TEST(vmaVirtualAllocate(virtualBlock, &allocCreateInfo, &allocData.virtualAlloc, nullptr) == VK_SUCCESS);
					}
					else
					{
						VmaAllocationCreateInfo allocCreateInfo = {};
						allocCreateInfo.pool = pool;
						switch (strategyIndex)
						{
						case 1: allocCreateInfo.flags = VMA_VIRTUAL_ALLOCATION_CREATE_STRATEGY_MIN_TIME_BIT; break;
						case 2: allocCreateInfo.flags = VMA_VIRTUAL_ALLOCATION_CREATE_STRATEGY_MIN_MEMORY_BIT; break;
						}
						VkMemoryRequirements req = {};
						req.size = allocSize;
						req.memoryTypeBits = UINT32_MAX;
						TEST(vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &allocData.alloc, nullptr) == VK_SUCCESS);
					}
					allocationsPerLevel[level].push_back(allocData);
				};

				auto destroyAllocation = [&](uint32_t level, size_t index) -> void
				{
					const AllocData& allocData = allocationsPerLevel[level][index];
					if (isVirtual)
						vmaVirtualFree(virtualBlock, allocData.virtualAlloc);
					else
						vmaFreeMemory(g_hAllocator, allocData.alloc);
					allocationsPerLevel[level].erase(allocationsPerLevel[level].begin() + index);
				};

				// Fill entire block with one big allocation.
				createAllocation(LEVEL_COUNT - 1);

				// For each level, remove one allocation and refill it with 2 allocations at lower level.
				for (uint32_t level = LEVEL_COUNT; level-- > 1; )
				{
					size_t indexToDestroy = rand.Generate() % allocationsPerLevel[level].size();
					destroyAllocation(level, indexToDestroy);
					createAllocation(level - 1);
					createAllocation(level - 1);
				}

				// Test statistics.
				{
					uint32_t actualAllocCount = 0, statAllocCount = 0;
					VkDeviceSize actualAllocSize = 0, statAllocSize = 0;
					// Calculate actual statistics.
					for (uint32_t level = 0; level < LEVEL_COUNT; ++level)
					{
						for (size_t index = allocationsPerLevel[level].size(); index--; )
						{
							if (isVirtual)
							{
								VmaVirtualAllocationInfo allocInfo = {};
								vmaGetVirtualAllocationInfo(virtualBlock, allocationsPerLevel[level][index].virtualAlloc, &allocInfo);
								actualAllocSize += allocInfo.size;
							}
							else
							{
								VmaAllocationInfo allocInfo = {};
								vmaGetAllocationInfo(g_hAllocator, allocationsPerLevel[level][index].alloc, &allocInfo);
								actualAllocSize += allocInfo.size;
							}
						}
						actualAllocCount += (uint32_t)allocationsPerLevel[level].size();
					}
					// Fetch reported statistics.
					if (isVirtual)
					{
						VmaDetailedStatistics info = {};
						vmaCalculateVirtualBlockStatistics(virtualBlock, &info);
						statAllocCount = info.statistics.allocationCount;
						statAllocSize = info.statistics.allocationBytes;
						TEST(info.statistics.blockCount == 1);
						TEST(info.statistics.blockBytes == blockSize);
					}
					else
					{
						VmaDetailedStatistics stats = {};
						vmaCalculatePoolStatistics(g_hAllocator, pool, &stats);
						statAllocCount = (uint32_t)stats.statistics.allocationCount;
						statAllocSize = stats.statistics.allocationBytes;
						TEST(stats.statistics.blockCount == 1);
						TEST(stats.statistics.blockBytes == blockSize);
					}
					// Compare them.
					TEST(actualAllocCount == statAllocCount);
					TEST(actualAllocSize == statAllocSize);
				}

				// Test JSON dump - for manual inspection.
				{
					char* json = nullptr;
					if (isVirtual)
					{
						vmaBuildVirtualBlockStatsString(virtualBlock, &json, VK_TRUE);
						int I = 1; // Put breakpoint here to inspect `json`.
						vmaFreeVirtualBlockStatsString(virtualBlock, json);
					}
					else
					{
						vmaBuildStatsString(g_hAllocator, &json, VK_TRUE);
						int I = 1; // Put breakpoint here to inspect `json`.
						vmaFreeStatsString(g_hAllocator, json);
					}
				}

				// Free all remaining allocations
				for (uint32_t level = 0; level < LEVEL_COUNT; ++level)
					for (size_t index = allocationsPerLevel[level].size(); index--; )
						destroyAllocation(level, index);
			}

			vmaDestroyVirtualBlock(virtualBlock);
			vmaDestroyPool(g_hAllocator, pool);
		}
	}
}

static void BasicTestTLSF()
{
	printf("Basic test TLSF\n");

	VmaVirtualBlock block;

	VmaVirtualBlockCreateInfo blockInfo = {};
	blockInfo.flags = 0;
	blockInfo.size = 50331648;
	vmaCreateVirtualBlock(&blockInfo, &block);

	VmaVirtualAllocationCreateInfo info = {};
	info.alignment = 2;

	VmaVirtualAllocation allocation[3] = {};

	info.size = 576;
	vmaVirtualAllocate(block, &info, allocation + 0, nullptr);

	info.size = 648;
	vmaVirtualAllocate(block, &info, allocation + 1, nullptr);

	vmaVirtualFree(block, allocation[0]);

	info.size = 720;
	vmaVirtualAllocate(block, &info, allocation + 2, nullptr);

	vmaVirtualFree(block, allocation[1]);
	vmaVirtualFree(block, allocation[2]);
	vmaDestroyVirtualBlock(block);
}

static void BasicTestAllocatePages()
{
	printf("Basic test allocate pages\n");

	RandomNumberGenerator rand{ 765461 };

	VkMemoryRequirements  req = {};
	req.size = 1024; // Whatever.
	req.memoryTypeBits = UINT32_MAX;

	VmaPoolCreateInfo poolCreateInfo = {};
	// 1 block of 1 MB.
	poolCreateInfo.blockSize = 1024 * 1024;
	poolCreateInfo.minBlockCount = poolCreateInfo.maxBlockCount = 1;

	// Create pool.
	VmaPool pool = nullptr;
	VkResult res = vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool);
	TEST(res == VK_SUCCESS);

	// Make 100 allocations of 4 KB - they should fit into the pool.
	VkMemoryRequirements memReq;
	memReq.memoryTypeBits = UINT32_MAX;
	memReq.alignment = 4 * 1024;
	memReq.size = 4 * 1024;

	VmaAllocationCreateInfo allocCreateInfo = {};
	allocCreateInfo.flags = VMA_ALLOCATION_CREATE_MAPPED_BIT;
	allocCreateInfo.pool = pool;

	constexpr uint32_t allocCount = 100;

	std::vector<VmaAllocation> alloc{ allocCount };
	std::vector<VmaAllocationInfo> allocInfo{ allocCount };
	res = vmaAllocateMemoryPages(g_hAllocator, &memReq, &allocCreateInfo, allocCount, alloc.data(), allocInfo.data());
	TEST(res == VK_SUCCESS);
	for (uint32_t i = 0; i < allocCount; ++i)
	{
		TEST(alloc[i] != VK_NULL_HANDLE &&
			allocInfo[i].pMappedData != nullptr &&
			allocInfo[i].deviceMemory == allocInfo[0].deviceMemory &&
			allocInfo[i].memoryType == allocInfo[0].memoryType);
	}

	// Free the allocations.
	vmaFreeMemoryPages(g_hAllocator, allocCount, alloc.data());
	std::fill(alloc.begin(), alloc.end(), nullptr);
	std::fill(allocInfo.begin(), allocInfo.end(), VmaAllocationInfo{});

	// Try to make 100 allocations of 100 KB. This call should fail due to not enough memory.
	// Also test optional allocationInfo = null.
	memReq.size = 100 * 1024;
	res = vmaAllocateMemoryPages(g_hAllocator, &memReq, &allocCreateInfo, allocCount, alloc.data(), nullptr);
	TEST(res != VK_SUCCESS);
	TEST(std::find_if(alloc.begin(), alloc.end(), [](VmaAllocation alloc) { return alloc != VK_NULL_HANDLE; }) == alloc.end());

	// Make 100 allocations of 4 KB, but with required alignment of 128 KB. This should also fail.
	memReq.size = 4 * 1024;
	memReq.alignment = 128 * 1024;
	res = vmaAllocateMemoryPages(g_hAllocator, &memReq, &allocCreateInfo, allocCount, alloc.data(), allocInfo.data());
	TEST(res != VK_SUCCESS);

	// Make 100 dedicated allocations of 4 KB.
	memReq.alignment = 4 * 1024;
	memReq.size = 4 * 1024;

	VmaAllocationCreateInfo dedicatedAllocCreateInfo = {};
	dedicatedAllocCreateInfo.requiredFlags = VK_MEMORY_PROPERTY_HOST_VISIBLE_BIT;
	dedicatedAllocCreateInfo.flags = VMA_ALLOCATION_CREATE_MAPPED_BIT | VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;
	res = vmaAllocateMemoryPages(g_hAllocator, &memReq, &dedicatedAllocCreateInfo, allocCount, alloc.data(), allocInfo.data());
	TEST(res == VK_SUCCESS);
	for (uint32_t i = 0; i < allocCount; ++i)
	{
		TEST(alloc[i] != VK_NULL_HANDLE &&
			allocInfo[i].pMappedData != nullptr &&
			allocInfo[i].memoryType == allocInfo[0].memoryType &&
			allocInfo[i].offset == 0);
		if (i > 0)
		{
			TEST(allocInfo[i].deviceMemory != allocInfo[0].deviceMemory);
		}
	}

	// Free the allocations.
	vmaFreeMemoryPages(g_hAllocator, allocCount, alloc.data());
	std::fill(alloc.begin(), alloc.end(), nullptr);
	std::fill(allocInfo.begin(), allocInfo.end(), VmaAllocationInfo{});

	vmaDestroyPool(g_hAllocator, pool);
}

static void TestMemoryPriority()
{
	printf("Test memory priority\n");

	VkMemoryRequirements req = {};
	req.size = 0x10000;
	req.memoryTypeBits = UINT32_MAX;

	VmaAllocationCreateInfo allocCreateInfo = {};
	allocCreateInfo.priority = 1.f;

	for (uint32_t testIndex = 0; testIndex < 2; ++testIndex)
	{
		// 1st is placed, 2nd is dedicated.
		if (testIndex == 1)
			allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_DEDICATED_MEMORY_BIT;

		BufferInfo bufInfo = {};
		VkResult res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo,
			&bufInfo.Allocation, nullptr);
		TEST(res == VK_SUCCESS);

		// There is nothing we can do to validate the priority.

		vmaFreeMemory(g_hAllocator, bufInfo.Allocation);
	}
}

static void TestPool_SameSize()
{
	printf("Test pool same size\n");

	const VkDeviceSize BUF_SIZE = 1024 * 1024;
	const size_t BUF_COUNT = 100;
	VkResult res;

	RandomNumberGenerator rand{ 123 };

	VkMemoryRequirements req = {0};
	req.size = BUF_SIZE;
	req.memoryTypeBits = UINT32_MAX;

	uint32_t memoryTypeBits = UINT32_MAX;

	VmaAllocationCreateInfo poolAllocInfo = {};
	poolAllocInfo.requiredFlags = VK_MEMORY_PROPERTY_HOST_VISIBLE_BIT | VK_MEMORY_PROPERTY_HOST_COHERENT_BIT | VK_MEMORY_PROPERTY_HOST_CACHED_BIT;
	uint32_t memTypeIndex;
	res = vmaFindMemoryTypeIndex(
		g_hAllocator,
		memoryTypeBits,
		&poolAllocInfo,
		&memTypeIndex);

	VmaPoolCreateInfo poolCreateInfo = {};
	poolCreateInfo.memoryTypeIndex = memTypeIndex;
	poolCreateInfo.blockSize = BUF_SIZE * BUF_COUNT / 4;
	poolCreateInfo.minBlockCount = 1;
	poolCreateInfo.maxBlockCount = 4;

	VmaPool pool;
	res = vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool);
	TEST(res == VK_SUCCESS);

	// Test pool name
	{
		static const char* const POOL_NAME = "Pool name";
		vmaSetPoolName(g_hAllocator, pool, POOL_NAME);

		const char* fetchedPoolName = nullptr;
		vmaGetPoolName(g_hAllocator, pool, &fetchedPoolName);
		TEST(strcmp(fetchedPoolName, POOL_NAME) == 0);

		vmaSetPoolName(g_hAllocator, pool, nullptr);
	}

	vmaSetCurrentFrameIndex(g_hAllocator, 1);

	VmaAllocationCreateInfo allocInfo = {};
	allocInfo.pool = pool;

	struct BufItem
	{
		VmaAllocation Alloc;
	};
	std::vector<BufItem> items;

	// Fill entire pool.
	for (size_t i = 0; i < BUF_COUNT; ++i)
	{
		BufItem item;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocInfo, &item.Alloc, nullptr);
		TEST(res == VK_SUCCESS);
		items.push_back(item);
	}

	// Make sure that another allocation would fail.
	{
		BufItem item;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocInfo,  &item.Alloc, nullptr);
		TEST(res == VK_ERROR_OUT_OF_DEVICE_MEMORY);
	}

	// Validate allocations.
	for (size_t i = 0; i < items.size(); ++i)
	{
		VmaAllocationInfo allocInfo;
		vmaGetAllocationInfo(g_hAllocator, items[i].Alloc, &allocInfo);
		TEST(allocInfo.deviceMemory != VK_NULL_HANDLE);
		TEST(allocInfo.pMappedData == nullptr);
	}

	// Free some percent of random items.
	{
		const size_t PERCENT_TO_FREE = 10;
		size_t itemsToFree = items.size() * PERCENT_TO_FREE / 100;
		for (size_t i = 0; i < itemsToFree; ++i)
		{
			size_t index = (size_t)rand.Generate() % items.size();
			vmaFreeMemory(g_hAllocator, items[index].Alloc);
			items.erase(items.begin() + index);
		}
	}

	// Randomly allocate and free items.
	{
		const size_t OPERATION_COUNT = BUF_COUNT;
		for (size_t i = 0; i < OPERATION_COUNT; ++i)
		{
			bool allocate = rand.Generate() % 2 != 0;
			if (allocate)
			{
				if (items.size() < BUF_COUNT)
				{
					BufItem item;
					res = vmaAllocateMemory(g_hAllocator, &req, &allocInfo, &item.Alloc, nullptr);
					if (res == VK_SUCCESS)
						items.push_back(item);
				}
			}
			else // Free
			{
				if (!items.empty())
				{
					size_t index = (size_t)rand.Generate() % items.size();
					vmaFreeMemory(g_hAllocator, items[index].Alloc);
					items.erase(items.begin() + index);
				}
			}
		}
	}

	// Allocate up to maximum.
	while (items.size() < BUF_COUNT)
	{
		BufItem item;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocInfo,  &item.Alloc, nullptr);
		TEST(res == VK_SUCCESS);
		items.push_back(item);
	}

	// Free one item.
	vmaFreeMemory(g_hAllocator, items.back().Alloc);
	items.pop_back();

	// Validate statistics.
	{
		VmaDetailedStatistics poolStats = {};
		vmaCalculatePoolStatistics(g_hAllocator, pool, &poolStats);
		TEST(poolStats.statistics.allocationCount == items.size());
		TEST(poolStats.statistics.blockBytes == BUF_COUNT * BUF_SIZE);
		TEST(poolStats.unusedRangeCount == 1);
		TEST(poolStats.statistics.blockBytes - poolStats.statistics.allocationBytes == BUF_SIZE);
	}

	// Free all remaining items.
	for (size_t i = items.size(); i--; )
		vmaFreeMemory(g_hAllocator, items[i].Alloc);
	items.clear();

	// Allocate maximum items again.
	for (size_t i = 0; i < BUF_COUNT; ++i)
	{
		BufItem item;
		res = vmaAllocateMemory(g_hAllocator, &req, &allocInfo, &item.Alloc, nullptr);
		TEST(res == VK_SUCCESS);
		items.push_back(item);
	}

	// Delete every other item.
	for (size_t i = 0; i < BUF_COUNT / 2; ++i)
	{
		vmaFreeMemory(g_hAllocator, items[i].Alloc);
		items.erase(items.begin() + i);
	}

	// Defragment!
	{
		VmaDefragmentationInfo defragmentationInfo = {};
		defragmentationInfo.flags = VMA_DEFRAGMENTATION_FLAG_ALGORITHM_FULL_BIT;
		defragmentationInfo.pool = pool;

		VmaDefragmentationContext defragCtx = nullptr;
		VkResult res = vmaBeginDefragmentation(g_hAllocator, &defragmentationInfo, &defragCtx);
		TEST(res == VK_SUCCESS);

		VmaDefragmentationPassMoveInfo pass;
		while ((res = vmaBeginDefragmentationPass(g_hAllocator, defragCtx, &pass)) == VK_INCOMPLETE)
		{
			if ((res = vmaEndDefragmentationPass(g_hAllocator, defragCtx, &pass)) == VK_SUCCESS)
				break;
			TEST(res == VK_INCOMPLETE);
		}
		TEST(res == VK_SUCCESS);

		VmaDefragmentationStats defragmentationStats;
		vmaEndDefragmentation(g_hAllocator, defragCtx, &defragmentationStats);
		TEST(defragmentationStats.allocationsMoved == 24);
	}

	// Free all remaining items.
	for (size_t i = items.size(); i--; )
		vmaFreeMemory(g_hAllocator, items[i].Alloc);
	items.clear();

	////////////////////////////////////////////////////////////////////////////////
	// Test for allocation too large for pool

	{
		VmaAllocationCreateInfo allocCreateInfo = {};
		allocCreateInfo.pool = pool;

		VkMemoryRequirements memReq;
		memReq.memoryTypeBits = UINT32_MAX;
		memReq.alignment = 1;
		memReq.size = poolCreateInfo.blockSize + 4;

		VmaAllocation alloc = nullptr;
		res = vmaAllocateMemory(g_hAllocator, &memReq, &allocCreateInfo, &alloc, nullptr);
		TEST(res == VK_ERROR_OUT_OF_DEVICE_MEMORY && alloc == nullptr);
	}

	vmaDestroyPool(g_hAllocator, pool);
}

static void TestVirtualBlocksAlgorithmsBenchmark()
{
	printf("Benchmark virtual blocks algorithms\n");
	printf("Alignment,Algorithm,Strategy,Alloc time ms,Random operation time ms,Free time ms\n");

	const size_t ALLOCATION_COUNT = 7200;
	const uint32_t MAX_ALLOC_SIZE = 2056;
	const size_t RANDOM_OPERATION_COUNT = ALLOCATION_COUNT * 2;

	VmaVirtualBlockCreateInfo blockCreateInfo = {};
	blockCreateInfo.size = 0;

	RandomNumberGenerator rand{ 20092010 };

	uint32_t allocSizes[ALLOCATION_COUNT];
	for (size_t i = 0; i < ALLOCATION_COUNT; ++i)
	{
		allocSizes[i] = rand.Generate() % MAX_ALLOC_SIZE + 1;
		blockCreateInfo.size += allocSizes[i];
	}
	blockCreateInfo.size = static_cast<VkDeviceSize>(blockCreateInfo.size * 2.5); // 150% size margin in case of buddy fragmentation

	for (uint8_t alignmentIndex = 0; alignmentIndex < 4; ++alignmentIndex)
	{
		VkDeviceSize alignment;
		switch (alignmentIndex)
		{
		case 0: alignment = 1; break;
		case 1: alignment = 16; break;
		case 2: alignment = 64; break;
		case 3: alignment = 256; break;
		default: assert(0); break;
		}

		for (uint8_t allocStrategyIndex = 0; allocStrategyIndex < 3; ++allocStrategyIndex)
		{
			VmaVirtualAllocationCreateFlags allocFlags;
			switch (allocStrategyIndex)
			{
			case 0: allocFlags = 0; break;
			case 1: allocFlags = VMA_VIRTUAL_ALLOCATION_CREATE_STRATEGY_MIN_MEMORY_BIT; break;
			case 2: allocFlags = VMA_VIRTUAL_ALLOCATION_CREATE_STRATEGY_MIN_TIME_BIT; break;
			default: assert(0);
			}

			for (uint8_t algorithmIndex = 0; algorithmIndex < 2; ++algorithmIndex)
			{
				switch (algorithmIndex)
				{
				case 0:
					blockCreateInfo.flags = (VmaVirtualBlockCreateFlagBits)0;
					break;
				case 1:
					blockCreateInfo.flags = VMA_VIRTUAL_BLOCK_CREATE_LINEAR_ALGORITHM_BIT;
					break;
				default:
					assert(0);
				}

				std::vector<VmaVirtualAllocation> allocs;
				allocs.reserve(ALLOCATION_COUNT + RANDOM_OPERATION_COUNT);
				allocs.resize(ALLOCATION_COUNT);
				VmaVirtualBlock block;
				TEST(vmaCreateVirtualBlock(&blockCreateInfo, &block) == VK_SUCCESS && block);

				// Alloc
				time_point timeBegin = std::chrono::high_resolution_clock::now();
				for (size_t i = 0; i < ALLOCATION_COUNT; ++i)
				{
					VmaVirtualAllocationCreateInfo allocCreateInfo = {};
					allocCreateInfo.size = allocSizes[i];
					allocCreateInfo.alignment = alignment;
					allocCreateInfo.flags = allocFlags;

					TEST(vmaVirtualAllocate(block, &allocCreateInfo, &allocs[i], nullptr) == VK_SUCCESS);
					TEST(allocs[i] != VK_NULL_HANDLE);
				}
				duration allocDuration = std::chrono::high_resolution_clock::now() - timeBegin;

				// Random operations
				timeBegin = std::chrono::high_resolution_clock::now();
				for (size_t opIndex = 0; opIndex < RANDOM_OPERATION_COUNT; ++opIndex)
				{
					if (rand.Generate() % 2)
					{
						VmaVirtualAllocationCreateInfo allocCreateInfo = {};
						allocCreateInfo.size = rand.Generate() % MAX_ALLOC_SIZE + 1;
						allocCreateInfo.alignment = alignment;
						allocCreateInfo.flags = allocFlags;

						VmaVirtualAllocation alloc;
						TEST(vmaVirtualAllocate(block, &allocCreateInfo, &alloc, nullptr) == VK_SUCCESS);
						TEST(alloc != VK_NULL_HANDLE);
						allocs.push_back(alloc);
					}
					else
					{
						size_t index = rand.Generate() % allocs.size();
						vmaVirtualFree(block, allocs[index]);
						if (index < allocs.size())
							allocs[index] = allocs.back();
						allocs.pop_back();
					}
				}
				duration randomDuration = std::chrono::high_resolution_clock::now() - timeBegin;

				// Free
				timeBegin = std::chrono::high_resolution_clock::now();
				for (size_t i = ALLOCATION_COUNT; i;)
					vmaVirtualFree(block, allocs[--i]);
				duration freeDuration = std::chrono::high_resolution_clock::now() - timeBegin;

				vmaDestroyVirtualBlock(block);

				printf("%llu,%s,%s,%g,%g,%g\n",
					(unsigned long long)alignment,
					VirtualAlgorithmToStr(blockCreateInfo.flags),
					GetVirtualAllocationStrategyName(allocFlags),
					ToFloatSeconds(allocDuration) * 1000.f,
					ToFloatSeconds(randomDuration) * 1000.f,
					ToFloatSeconds(freeDuration) * 1000.f);
			}
		}
	}
}

void TestDefragmentationVsMapping()
{
	printf("Test defragmentation vs mapping\n");

	VkMemoryRequirements req = {};
	req.size = 64 * KILOBYTE;
	req.memoryTypeBits = UINT32_MAX;

	VmaAllocationCreateInfo dummyAllocCreateInfo = {};
	dummyAllocCreateInfo.flags = VMA_ALLOCATION_CREATE_HOST_ACCESS_SEQUENTIAL_WRITE_BIT;

	VmaPoolCreateInfo poolCreateInfo = {};
	poolCreateInfo.flags = VMA_POOL_CREATE_IGNORE_BUFFER_IMAGE_GRANULARITY_BIT;
	poolCreateInfo.blockSize = 1 * MEGABYTE;

	VmaPool pool = VK_NULL_HANDLE;
	TEST(vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool) == VK_SUCCESS);

	RandomNumberGenerator rand{ 2355762 };

	// 16 * 64 KB allocations fit into a single 1 MB block. Create 10 such blocks.
	constexpr uint32_t START_ALLOC_COUNT = 160;
	std::vector<AllocInfo> allocs{ START_ALLOC_COUNT };

	constexpr uint32_t RAND_NUM_PERSISTENTLY_MAPPED_BIT = 0x1000;
	constexpr uint32_t RAND_NUM_MANUAL_MAP_COUNT_MASK = 0x3;

	// Create all the allocations, map what's needed.
	{
		VmaAllocationCreateInfo allocCreateInfo = {};
		allocCreateInfo.pool = pool;
		for (size_t allocIndex = 0; allocIndex < START_ALLOC_COUNT; ++allocIndex)
		{
			const uint32_t randNum = rand.Generate();
			if (randNum & RAND_NUM_PERSISTENTLY_MAPPED_BIT)
				allocCreateInfo.flags |= VMA_ALLOCATION_CREATE_MAPPED_BIT;
			else
				allocCreateInfo.flags &= ~VMA_ALLOCATION_CREATE_MAPPED_BIT;
			allocs[allocIndex].AllocMemory(req, allocCreateInfo);
			vmaSetAllocationUserData(g_hAllocator, allocs[allocIndex].m_Allocation, (void*)(uintptr_t)randNum);
		}
	}

	// Destroy 2/3 of them.
	for (uint32_t i = 0; i < START_ALLOC_COUNT * 2 / 3; ++i)
	{
		const uint32_t allocIndexToRemove = rand.Generate() % allocs.size();
		allocs[allocIndexToRemove].Destroy();
		allocs.erase(allocs.begin() + allocIndexToRemove);
	}

	// Map the remaining allocations the right number of times.
	for (size_t allocIndex = 0, allocCount = allocs.size(); allocIndex < allocCount; ++allocIndex)
	{
		VmaAllocationInfo allocInfo;
		vmaGetAllocationInfo(g_hAllocator, allocs[allocIndex].m_Allocation, &allocInfo);
		const uint32_t randNum = (uint32_t)(uintptr_t)allocInfo.pUserData;
		const uint32_t mapCount = randNum & RAND_NUM_MANUAL_MAP_COUNT_MASK;
		for (uint32_t mapIndex = 0; mapIndex < mapCount; ++mapIndex)
		{
			void* ptr;
			TEST(vmaMapMemory(g_hAllocator, allocs[allocIndex].m_Allocation, &ptr) == VK_SUCCESS);
			TEST(ptr != nullptr);
		}
	}

	// Defragment!
	{
		VmaDefragmentationInfo defragInfo = {};
		defragInfo.pool = pool;
		defragInfo.flags = VMA_DEFRAGMENTATION_FLAG_ALGORITHM_EXTENSIVE_BIT;
		VmaDefragmentationContext defragCtx;
		TEST(vmaBeginDefragmentation(g_hAllocator, &defragInfo, &defragCtx) == VK_SUCCESS);

		for (uint32_t passIndex = 0; ; ++passIndex)
		{
			VmaDefragmentationPassMoveInfo passInfo = {};
			VkResult res = vmaBeginDefragmentationPass(g_hAllocator, defragCtx, &passInfo);
			if (res == VK_SUCCESS)
				break;
			TEST(res == VK_INCOMPLETE);

			printf("    Pass %u moving %u allocations\n", passIndex, passInfo.moveCount);

			for (uint32_t moveIndex = 0; moveIndex < passInfo.moveCount; ++moveIndex)
			{
				if (rand.Generate() % 5 == 0)
					passInfo.pMoves[moveIndex].operation = VMA_DEFRAGMENTATION_MOVE_OPERATION_IGNORE;
			}


			res = vmaEndDefragmentationPass(g_hAllocator, defragCtx, &passInfo);
			if (res == VK_SUCCESS)
				break;
			TEST(res == VK_INCOMPLETE);
		}

		VmaDefragmentationStats defragStats = {};
		vmaEndDefragmentation(g_hAllocator, defragCtx, &defragStats);
		printf("    Defragmentation: moved %u allocations, %llu B, freed %u memory blocks, %llu B\n",
			defragStats.allocationsMoved, (long long)defragStats.bytesMoved,
			defragStats.deviceMemoryBlocksFreed, (long long)defragStats.bytesFreed);
		TEST(defragStats.allocationsMoved > 0 && defragStats.bytesMoved > 0);
		TEST(defragStats.deviceMemoryBlocksFreed > 0 && defragStats.bytesFreed > 0);
	}

	// Test mapping and unmap
	for (size_t allocIndex = allocs.size(); allocIndex--; )
	{
		VmaAllocationInfo allocInfo;
		vmaGetAllocationInfo(g_hAllocator, allocs[allocIndex].m_Allocation, &allocInfo);
		const uint32_t randNum = (uint32_t)(uintptr_t)allocInfo.pUserData;
		const bool isMapped = (randNum & (RAND_NUM_PERSISTENTLY_MAPPED_BIT | RAND_NUM_MANUAL_MAP_COUNT_MASK)) != 0;
		TEST(isMapped == (allocInfo.pMappedData != nullptr));

		const uint32_t mapCount = randNum & RAND_NUM_MANUAL_MAP_COUNT_MASK;
		for (uint32_t mapIndex = 0; mapIndex < mapCount; ++mapIndex)
			vmaUnmapMemory(g_hAllocator, allocs[allocIndex].m_Allocation);
	}

	// Destroy all the remaining allocations.
	for (size_t i = allocs.size(); i--; )
		allocs[i].Destroy();

	vmaDestroyPool(g_hAllocator, pool);
}

enum CONFIG_TYPE
{
	CONFIG_TYPE_MINIMUM,
	CONFIG_TYPE_SMALL,
	CONFIG_TYPE_AVERAGE,
	CONFIG_TYPE_LARGE,
	CONFIG_TYPE_MAXIMUM,
	CONFIG_TYPE_COUNT
};

static constexpr CONFIG_TYPE ConfigType = CONFIG_TYPE_AVERAGE;
enum class FREE_ORDER { FORWARD, BACKWARD, RANDOM, COUNT };

static const char* FREE_ORDER_NAMES[] =
{
	"FORWARD",
	"BACKWARD",
	"RANDOM",
};

static uint32_t GetAllocationStrategyCount()
{
	switch (ConfigType)
	{
	case CONFIG_TYPE_MINIMUM:
	case CONFIG_TYPE_SMALL:
		return 1;
	default: assert(0);
	case CONFIG_TYPE_AVERAGE:
	case CONFIG_TYPE_LARGE:
	case CONFIG_TYPE_MAXIMUM:
		return 2;
	}
}

// Wrapper for RandomNumberGenerator compatible with STL "UniformRandomNumberGenerator" idea.
struct MyUniformRandomNumberGenerator
{
	typedef uint32_t result_type;
	MyUniformRandomNumberGenerator(RandomNumberGenerator& gen) : m_Gen(gen) { }
	static uint32_t min() { return 0; }
	static uint32_t max() { return UINT32_MAX; }
	uint32_t operator()() { return m_Gen.Generate(); }

private:
	RandomNumberGenerator& m_Gen;
};

// Copy of internal VmaAlgorithmToStr.
static const char* AlgorithmToStr(uint32_t algorithm)
{
	switch (algorithm)
	{
	case VMA_POOL_CREATE_LINEAR_ALGORITHM_BIT:
		return "Linear";
	case 0:
		return "TLSF";
	default:
		assert(0);
		return "";
	}
}

static const char* GetAllocationStrategyName(VmaAllocationCreateFlags allocStrategy)
{
	switch (allocStrategy)
	{
	case VMA_ALLOCATION_CREATE_STRATEGY_MIN_MEMORY_BIT: return "MIN_MEMORY"; break;
	case VMA_ALLOCATION_CREATE_STRATEGY_MIN_TIME_BIT: return "MIN_TIME"; break;
	case 0: return "Default"; break;
	default: assert(0); return "";
	}
}

static void CurrentTimeToStr(std::string& out)
{
	time_t rawTime; time(&rawTime);
	struct tm timeInfo; 
#ifdef _WIN32
	localtime_s(&timeInfo, &rawTime);
#else
	localtime_r(&rawTime, &timeInfo);
#endif
	char timeStr[128];
	strftime(timeStr, 128, "%c", &timeInfo);
	out = timeStr;
}

static const char* CODE_DESCRIPTION = "Foo";

static void BenchmarkAlgorithmsCase(FILE* file,
	uint32_t algorithm,
	bool empty,
	VmaAllocationCreateFlags allocStrategy,
	FREE_ORDER freeOrder)
{
	RandomNumberGenerator rand{ 16223 };

	const VkDeviceSize bufSizeMin = 32;
	const VkDeviceSize bufSizeMax = 1024;
	const size_t maxBufCapacity = 10000;
	const uint32_t iterationCount = 10;

	VkMemoryRequirements req = {};
	req.size = bufSizeMax;
	req.memoryTypeBits = UINT32_MAX;

	VmaPoolCreateInfo poolCreateInfo = {};
	poolCreateInfo.blockSize = bufSizeMax * maxBufCapacity;
	poolCreateInfo.flags = VMA_POOL_CREATE_IGNORE_BUFFER_IMAGE_GRANULARITY_BIT;//TODO remove this
	poolCreateInfo.flags |= algorithm;
	poolCreateInfo.minBlockCount = poolCreateInfo.maxBlockCount = 1;

	VmaPool pool = nullptr;
	VkResult res = vmaCreatePool(g_hAllocator, &poolCreateInfo, &pool);
	TEST(res == VK_SUCCESS);

	VmaAllocationCreateInfo allocCreateInfo = {};
	allocCreateInfo.pool = pool;
	allocCreateInfo.flags = allocStrategy;

	VmaAllocation alloc;
	std::vector<VmaAllocation> baseAllocations;

	if (!empty)
	{
		// Make allocations up to 1/3 of pool size.
		VkDeviceSize totalSize = 0;
		while (totalSize < poolCreateInfo.blockSize / 3)
		{
			// This test intentionally allows sizes that are aligned to 4 or 16 bytes.
			// This is theoretically allowed and already uncovered one bug.
			req.size = bufSizeMin + rand.Generate() % (bufSizeMax - bufSizeMin);
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, nullptr);
			TEST(res == VK_SUCCESS);
			baseAllocations.push_back(alloc);
			totalSize += req.size;
		}

		// Delete half of them, choose randomly.
		size_t allocsToDelete = baseAllocations.size() / 2;
		for (size_t i = 0; i < allocsToDelete; ++i)
		{
			const size_t index = (size_t)rand.Generate() % baseAllocations.size();
			vmaFreeMemory(g_hAllocator, baseAllocations[index]);
			baseAllocations.erase(baseAllocations.begin() + index);
		}
	}

	// BENCHMARK
	const size_t allocCount = maxBufCapacity / 3;
	std::vector<VmaAllocation> testAllocations;
	testAllocations.reserve(allocCount);
	duration allocTotalDuration = duration::zero();
	duration freeTotalDuration = duration::zero();
	for (uint32_t iterationIndex = 0; iterationIndex < iterationCount; ++iterationIndex)
	{
		// Allocations
		time_point allocTimeBeg = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < allocCount; ++i)
		{
			req.size = bufSizeMin + rand.Generate() % (bufSizeMax - bufSizeMin);
			res = vmaAllocateMemory(g_hAllocator, &req, &allocCreateInfo, &alloc, nullptr);
			TEST(res == VK_SUCCESS);
			testAllocations.push_back(alloc);
		}
		allocTotalDuration += std::chrono::high_resolution_clock::now() - allocTimeBeg;

		// Deallocations
		switch (freeOrder)
		{
		case FREE_ORDER::FORWARD:
			// Leave testAllocations unchanged.
			break;
		case FREE_ORDER::BACKWARD:
			std::reverse(testAllocations.begin(), testAllocations.end());
			break;
		case FREE_ORDER::RANDOM:
			std::shuffle(testAllocations.begin(), testAllocations.end(), MyUniformRandomNumberGenerator(rand));
			break;
		default: assert(0);
		}

		time_point freeTimeBeg = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < allocCount; ++i)
			vmaFreeMemory(g_hAllocator, testAllocations[i]);
		freeTotalDuration += std::chrono::high_resolution_clock::now() - freeTimeBeg;

		testAllocations.clear();
	}

	// Delete baseAllocations
	while (!baseAllocations.empty())
	{
		vmaFreeMemory(g_hAllocator, baseAllocations.back());
		baseAllocations.pop_back();
	}

	vmaDestroyPool(g_hAllocator, pool);

	const float allocTotalSeconds = ToFloatSeconds(allocTotalDuration);
	const float freeTotalSeconds = ToFloatSeconds(freeTotalDuration);

	printf("    Algorithm=%s %s Allocation=%s FreeOrder=%s: allocations %g s, free %g s\n",
		AlgorithmToStr(algorithm),
		empty ? "Empty" : "Not empty",
		GetAllocationStrategyName(allocStrategy),
		FREE_ORDER_NAMES[(size_t)freeOrder],
		allocTotalSeconds,
		freeTotalSeconds);

	if (file)
	{
		std::string currTime;
		CurrentTimeToStr(currTime);

		fprintf(file, "%s,%s,%s,%u,%s,%s,%g,%g\n",
			CODE_DESCRIPTION, currTime.c_str(),
			AlgorithmToStr(algorithm),
			empty ? 1 : 0,
			GetAllocationStrategyName(allocStrategy),
			FREE_ORDER_NAMES[(uint32_t)freeOrder],
			allocTotalSeconds,
			freeTotalSeconds);
	}
}

static void BenchmarkAlgorithms(FILE* file)
{
	printf("Benchmark algorithms\n");

	if (file)
	{
		fprintf(file,
			"Code,Time,"
			"Algorithm,Empty,Allocation strategy,Free order,"
			"Allocation time (s),Deallocation time (s)\n");
	}

	uint32_t freeOrderCount = 1;
	if (ConfigType >= CONFIG_TYPE::CONFIG_TYPE_LARGE)
		freeOrderCount = 3;
	else if (ConfigType >= CONFIG_TYPE::CONFIG_TYPE_SMALL)
		freeOrderCount = 2;

	const uint32_t emptyCount = ConfigType >= CONFIG_TYPE::CONFIG_TYPE_SMALL ? 2 : 1;
	const uint32_t allocStrategyCount = GetAllocationStrategyCount();

	for (uint32_t freeOrderIndex = 0; freeOrderIndex < freeOrderCount; ++freeOrderIndex)
	{
		FREE_ORDER freeOrder = FREE_ORDER::COUNT;
		switch (freeOrderIndex)
		{
		case 0: freeOrder = FREE_ORDER::BACKWARD; break;
		case 1: freeOrder = FREE_ORDER::FORWARD; break;
		case 2: freeOrder = FREE_ORDER::RANDOM; break;
		default: assert(0);
		}

		for (uint32_t emptyIndex = 0; emptyIndex < emptyCount; ++emptyIndex)
		{
			for (uint32_t algorithmIndex = 0; algorithmIndex < 2; ++algorithmIndex)
			{
				uint32_t algorithm = 0;
				switch (algorithmIndex)
				{
				case 0:
					break;
				case 1:
					algorithm = VMA_POOL_CREATE_LINEAR_ALGORITHM_BIT;
					break;
				default:
					assert(0);
				}

				uint32_t currAllocStrategyCount = algorithm != 0 ? 1 : allocStrategyCount;
				for (uint32_t allocStrategyIndex = 0; allocStrategyIndex < currAllocStrategyCount; ++allocStrategyIndex)
				{
					VmaAllocatorCreateFlags strategy = 0;
					if (currAllocStrategyCount > 1)
					{
						switch (allocStrategyIndex)
						{
						case 0: strategy = VMA_ALLOCATION_CREATE_STRATEGY_MIN_MEMORY_BIT; break;
						case 1: strategy = VMA_ALLOCATION_CREATE_STRATEGY_MIN_TIME_BIT; break;
						default: assert(0);
						}
					}

					BenchmarkAlgorithmsCase(
						file,
						algorithm,
						(emptyIndex == 0), // empty
						strategy,
						freeOrder); // freeOrder
				}
			}
		}
	}
}

struct AllocationSize
{
	uint32_t Probability;
	VkDeviceSize BufferSizeMin, BufferSizeMax;
	uint32_t ImageSizeMin, ImageSizeMax;
};

struct Config
{
	uint32_t RandSeed;
	VkDeviceSize BeginBytesToAllocate;
	uint32_t AdditionalOperationCount;
	VkDeviceSize MaxBytesToAllocate;
	uint32_t MemUsageProbability[4]; // For VMA_MEMORY_USAGE_*
	std::vector<AllocationSize> AllocationSizes;
	uint32_t ThreadCount;
	uint32_t ThreadsUsingCommonAllocationsProbabilityPercent;
	FREE_ORDER FreeOrder;
	VmaAllocationCreateFlags AllocationStrategy; // For VMA_ALLOCATION_CREATE_STRATEGY_*
};

struct Result
{
	duration TotalTime;
	duration AllocationTimeMin, AllocationTimeAvg, AllocationTimeMax;
	duration DeallocationTimeMin, DeallocationTimeAvg, DeallocationTimeMax;
	VkDeviceSize TotalMemoryAllocated;
	VkDeviceSize FreeRangeSizeAvg, FreeRangeSizeMax;
};

static void WriteMainTestResultHeader(FILE* file)
{
	fprintf(file,
		"Code,Time,"
		"Threads,Buffers and images,Sizes,Operations,Allocation strategy,Free order,"
		"Total Time (us),"
		"Allocation Time Min (us),"
		"Allocation Time Avg (us),"
		"Allocation Time Max (us),"
		"Deallocation Time Min (us),"
		"Deallocation Time Avg (us),"
		"Deallocation Time Max (us),"
		"Total Memory Allocated (B),"
		"Free Range Size Avg (B),"
		"Free Range Size Max (B)\n");
}

static void WriteMainTestResult(
	FILE* file,
	const char* codeDescription,
	const char* testDescription,
	const Config& config, const Result& result)
{
	float totalTimeSeconds = ToFloatSeconds(result.TotalTime);
	float allocationTimeMinSeconds = ToFloatSeconds(result.AllocationTimeMin);
	float allocationTimeAvgSeconds = ToFloatSeconds(result.AllocationTimeAvg);
	float allocationTimeMaxSeconds = ToFloatSeconds(result.AllocationTimeMax);
	float deallocationTimeMinSeconds = ToFloatSeconds(result.DeallocationTimeMin);
	float deallocationTimeAvgSeconds = ToFloatSeconds(result.DeallocationTimeAvg);
	float deallocationTimeMaxSeconds = ToFloatSeconds(result.DeallocationTimeMax);

	std::string currTime;
	CurrentTimeToStr(currTime);

	fprintf(file,
		"%s,%s,%s,"
		"%.2f,%.2f,%.2f,%.2f,%.2f,%.2f,%.2f,%llu,%llu,%llu\n",
		codeDescription,
		currTime.c_str(),
		testDescription,
		totalTimeSeconds * 1e6f,
		allocationTimeMinSeconds * 1e6f,
		allocationTimeAvgSeconds * 1e6f,
		allocationTimeMaxSeconds * 1e6f,
		deallocationTimeMinSeconds * 1e6f,
		deallocationTimeAvgSeconds * 1e6f,
		deallocationTimeMaxSeconds * 1e6f,
		(long long)result.TotalMemoryAllocated,
		(long long)result.FreeRangeSizeAvg,
		(long long)result.FreeRangeSizeMax);
}


static void InitResult(Result& outResult)
{
	outResult.TotalTime = duration::zero();
	outResult.AllocationTimeMin = duration::max();
	outResult.AllocationTimeAvg = duration::zero();
	outResult.AllocationTimeMax = duration::min();
	outResult.DeallocationTimeMin = duration::max();
	outResult.DeallocationTimeAvg = duration::zero();
	outResult.DeallocationTimeMax = duration::min();
	outResult.TotalMemoryAllocated = 0;
	outResult.FreeRangeSizeAvg = 0;
	outResult.FreeRangeSizeMax = 0;
}

class TimeRegisterObj
{
public:
	TimeRegisterObj(duration& min, duration& sum, duration& max) :
		m_Min(min),
		m_Sum(sum),
		m_Max(max),
		m_TimeBeg(std::chrono::high_resolution_clock::now())
	{
	}

	~TimeRegisterObj()
	{
		duration d = std::chrono::high_resolution_clock::now() - m_TimeBeg;
		m_Sum += d;
		if (d < m_Min) m_Min = d;
		if (d > m_Max) m_Max = d;
	}

private:
	duration& m_Min;
	duration& m_Sum;
	duration& m_Max;
	time_point m_TimeBeg;
};

class AllocationTimeRegisterObj : public TimeRegisterObj
{
public:
	AllocationTimeRegisterObj(Result& result) :
		TimeRegisterObj(result.AllocationTimeMin, result.AllocationTimeAvg, result.AllocationTimeMax)
	{
	}
};

class DeallocationTimeRegisterObj : public TimeRegisterObj
{
public:
	DeallocationTimeRegisterObj(Result& result) :
		TimeRegisterObj(result.DeallocationTimeMin, result.DeallocationTimeAvg, result.DeallocationTimeMax)
	{
	}
};

template <typename T>
inline T round_div(T x, T y)
{
	return (x + y / (T)2) / y;
}

VkResult MainTest(Result& outResult, const Config& config)
{
	assert(config.ThreadCount > 0);

	InitResult(outResult);

	RandomNumberGenerator mainRand{ config.RandSeed };

	time_point timeBeg = std::chrono::high_resolution_clock::now();

	std::atomic<size_t> allocationCount{0};
	VkResult res = VK_SUCCESS;

	uint32_t memUsageProbabilitySum =
		config.MemUsageProbability[0] + config.MemUsageProbability[1] +
		config.MemUsageProbability[2] + config.MemUsageProbability[3];
	assert(memUsageProbabilitySum > 0);

	uint32_t allocationSizeProbabilitySum = std::accumulate(
		config.AllocationSizes.begin(),
		config.AllocationSizes.end(),
		0u,
		[](uint32_t sum, const AllocationSize& allocSize) {
		return sum + allocSize.Probability;
	});

	struct Allocation
	{
		VmaAllocation Alloc;
	};

	std::vector<Allocation> commonAllocations;
	std::mutex commonAllocationsMutex;

	auto Allocate = [&](
		VkDeviceSize bufferSize,
		RandomNumberGenerator& localRand,
		VkDeviceSize& totalAllocatedBytes,
		std::vector<Allocation>& allocations) -> VkResult
	{
		uint32_t memUsageIndex = 0;
		uint32_t memUsageRand = localRand.Generate() % memUsageProbabilitySum;
		while (memUsageRand >= config.MemUsageProbability[memUsageIndex])
			memUsageRand -= config.MemUsageProbability[memUsageIndex++];

		VmaAllocationCreateInfo memReq = {};
		memReq.usage = (VmaMemoryUsage)(VMA_MEMORY_USAGE_GPU_ONLY + memUsageIndex);
		memReq.flags |= config.AllocationStrategy;

		Allocation allocation = {};
		VmaAllocationInfo allocationInfo;

		// Buffer
		if (bufferSize > 0)
		{
			VkMemoryRequirements req = {};
			req.size = bufferSize;
			req.memoryTypeBits = UINT32_MAX;
			{
				AllocationTimeRegisterObj timeRegisterObj{ outResult };
				res = vmaAllocateMemory(g_hAllocator, &req, &memReq, &allocation.Alloc, &allocationInfo);
			}

			if (res == VK_SUCCESS)
			{
				++allocationCount;
				totalAllocatedBytes += allocationInfo.size;
				bool useCommonAllocations = localRand.Generate() % 100 < config.ThreadsUsingCommonAllocationsProbabilityPercent;
				if (useCommonAllocations)
				{
					std::unique_lock<std::mutex> lock(commonAllocationsMutex);
					commonAllocations.push_back(allocation);
				}
				else
					allocations.push_back(allocation);
			}
			else
			{
				TEST(0);
			}
		}
		
		return res;
	};

	auto GetNextAllocationSize = [&](
		VkDeviceSize& outBufSize,
		RandomNumberGenerator& localRand)
	{
		outBufSize = 0;

		uint32_t allocSizeIndex = 0;
		uint32_t r = localRand.Generate() % allocationSizeProbabilitySum;
		while (r >= config.AllocationSizes[allocSizeIndex].Probability)
			r -= config.AllocationSizes[allocSizeIndex++].Probability;

		const AllocationSize& allocSize = config.AllocationSizes[allocSizeIndex];
		if (allocSize.BufferSizeMax > 0)
		{
			assert(allocSize.ImageSizeMax == 0);
			if (allocSize.BufferSizeMax == allocSize.BufferSizeMin)
				outBufSize = allocSize.BufferSizeMin;
			else
			{
				outBufSize = allocSize.BufferSizeMin + localRand.Generate() % (allocSize.BufferSizeMax - allocSize.BufferSizeMin);
				outBufSize = outBufSize / 16 * 16;
			}
		}
	};

	std::atomic<uint32_t> numThreadsReachedMaxAllocations{0};
	std::condition_variable cv;
	std::mutex mtx;
	bool valid_flag = false;

	auto ThreadProc = [&](uint32_t randSeed) -> void
	{
		RandomNumberGenerator threadRand(randSeed);
		VkDeviceSize threadTotalAllocatedBytes = 0;
		std::vector<Allocation> threadAllocations;
		VkDeviceSize threadBeginBytesToAllocate = config.BeginBytesToAllocate / config.ThreadCount;
		VkDeviceSize threadMaxBytesToAllocate = config.MaxBytesToAllocate / config.ThreadCount;
		uint32_t threadAdditionalOperationCount = config.AdditionalOperationCount / config.ThreadCount;

		// BEGIN ALLOCATIONS
		for (;;)
		{
			VkDeviceSize bufferSize = 0;
			GetNextAllocationSize(bufferSize, threadRand);
			if (threadTotalAllocatedBytes + bufferSize  <
				threadBeginBytesToAllocate)
			{
				if (Allocate(bufferSize, threadRand, threadTotalAllocatedBytes, threadAllocations) != VK_SUCCESS)
					break;
			}
			else
				break;
		}

		// ADDITIONAL ALLOCATIONS AND FREES
		for (size_t i = 0; i < threadAdditionalOperationCount; ++i)
		{
			VkDeviceSize bufferSize = 0;
			GetNextAllocationSize(bufferSize, threadRand);

			// true = allocate, false = free
			bool allocate = threadRand.Generate() % 2 != 0;

			if (allocate)
			{
				if (threadTotalAllocatedBytes +
					bufferSize  <
					threadMaxBytesToAllocate)
				{
					if (Allocate(bufferSize, threadRand, threadTotalAllocatedBytes, threadAllocations) != VK_SUCCESS)
						break;
				}
			}
			else
			{
				bool useCommonAllocations = threadRand.Generate() % 100 < config.ThreadsUsingCommonAllocationsProbabilityPercent;
				if (useCommonAllocations)
				{
					std::unique_lock<std::mutex> lock(commonAllocationsMutex);
					if (!commonAllocations.empty())
					{
						size_t indexToFree = threadRand.Generate() % commonAllocations.size();
						VmaAllocationInfo allocationInfo;
						vmaGetAllocationInfo(g_hAllocator, commonAllocations[indexToFree].Alloc, &allocationInfo);
						if (threadTotalAllocatedBytes >= allocationInfo.size)
						{
							DeallocationTimeRegisterObj timeRegisterObj{ outResult };
							if (commonAllocations[indexToFree].Alloc != VK_NULL_HANDLE)
								vmaFreeMemory(g_hAllocator, commonAllocations[indexToFree].Alloc);
							threadTotalAllocatedBytes -= allocationInfo.size;
							commonAllocations.erase(commonAllocations.begin() + indexToFree);
						}
					}
				}
				else
				{
					if (!threadAllocations.empty())
					{
						size_t indexToFree = threadRand.Generate() % threadAllocations.size();
						VmaAllocationInfo allocationInfo;
						vmaGetAllocationInfo(g_hAllocator, threadAllocations[indexToFree].Alloc, &allocationInfo);
						if (threadTotalAllocatedBytes >= allocationInfo.size)
						{
							DeallocationTimeRegisterObj timeRegisterObj{ outResult };
							if (threadAllocations[indexToFree].Alloc != VK_NULL_HANDLE)
								vmaFreeMemory(g_hAllocator,  threadAllocations[indexToFree].Alloc);
							threadTotalAllocatedBytes -= allocationInfo.size;
							threadAllocations.erase(threadAllocations.begin() + indexToFree);
						}
					}
				}
			}
		}

		++numThreadsReachedMaxAllocations;

		std::unique_lock<std::mutex> lk(mtx);
		cv.wait(lk, [&]{return valid_flag;});
		valid_flag = false;

		// DEALLOCATION
		while (!threadAllocations.empty())
		{
			size_t indexToFree = 0;
			switch (config.FreeOrder)
			{
			case FREE_ORDER::FORWARD:
				indexToFree = 0;
				break;
			case FREE_ORDER::BACKWARD:
				indexToFree = threadAllocations.size() - 1;
				break;
			case FREE_ORDER::RANDOM:
				indexToFree = mainRand.Generate() % threadAllocations.size();
				break;
			}

			{
				DeallocationTimeRegisterObj timeRegisterObj{ outResult };
				if (threadAllocations[indexToFree].Alloc != VK_NULL_HANDLE)
					vmaFreeMemory(g_hAllocator, threadAllocations[indexToFree].Alloc);
			}
			threadAllocations.erase(threadAllocations.begin() + indexToFree);
		}
		valid_flag = true;
		cv.notify_one();
	};

	uint32_t threadRandSeed = mainRand.Generate();
	std::vector<std::thread> bkgThreads;
	for (size_t i = 0; i < config.ThreadCount; ++i)
	{
		bkgThreads.emplace_back(std::bind(ThreadProc, threadRandSeed + (uint32_t)i));
	}

	// Wait for threads reached max allocations
	while (numThreadsReachedMaxAllocations < config.ThreadCount)
		std::this_thread::yield();

	// CALCULATE MEMORY STATISTICS ON FINAL USAGE
	VmaTotalStatistics vmaStats = {};
	vmaCalculateStatistics(g_hAllocator, &vmaStats);
	outResult.TotalMemoryAllocated = vmaStats.total.statistics.blockBytes;
	outResult.FreeRangeSizeMax = vmaStats.total.unusedRangeSizeMax;
	outResult.FreeRangeSizeAvg = round_div<VkDeviceSize>(vmaStats.total.statistics.blockBytes - vmaStats.total.statistics.allocationBytes, vmaStats.total.unusedRangeCount);

	// Signal threads to deallocate
	valid_flag = true;
	cv.notify_one();

	// Wait for threads finished
	for (size_t i = 0; i < bkgThreads.size(); ++i)
		bkgThreads[i].join();
	bkgThreads.clear();

	// Deallocate remaining common resources
	while (!commonAllocations.empty())
	{
		size_t indexToFree = 0;
		switch (config.FreeOrder)
		{
		case FREE_ORDER::FORWARD:
			indexToFree = 0;
			break;
		case FREE_ORDER::BACKWARD:
			indexToFree = commonAllocations.size() - 1;
			break;
		case FREE_ORDER::RANDOM:
			indexToFree = mainRand.Generate() % commonAllocations.size();
			break;
		}

		{
			DeallocationTimeRegisterObj timeRegisterObj{ outResult };
			if (commonAllocations[indexToFree].Alloc != VK_NULL_HANDLE)
				vmaFreeMemory(g_hAllocator, commonAllocations[indexToFree].Alloc);
		}
		commonAllocations.erase(commonAllocations.begin() + indexToFree);
	}

	if (allocationCount)
	{
		outResult.AllocationTimeAvg /= allocationCount;
		outResult.DeallocationTimeAvg /= allocationCount;
	}

	outResult.TotalTime = std::chrono::high_resolution_clock::now() - timeBeg;

	return res;
}

static void PerformMainTests(FILE* file)
{
	printf("MAIN TESTS:\n");

	uint32_t repeatCount = 1;
	if (ConfigType >= CONFIG_TYPE_MAXIMUM) repeatCount = 3;

	Config config{};
	config.RandSeed = 65735476;
	config.MemUsageProbability[0] = 1; // VMA_MEMORY_USAGE_GPU_ONLY
	config.FreeOrder = FREE_ORDER::FORWARD;

	size_t threadCountCount = 1;
	switch (ConfigType)
	{
	case CONFIG_TYPE_MINIMUM: threadCountCount = 1; break;
	case CONFIG_TYPE_SMALL:   threadCountCount = 2; break;
	case CONFIG_TYPE_AVERAGE: threadCountCount = 3; break;
	case CONFIG_TYPE_LARGE:   threadCountCount = 5; break;
	case CONFIG_TYPE_MAXIMUM: threadCountCount = 7; break;
	default: assert(0);
	}

	const size_t strategyCount = GetAllocationStrategyCount();

	for (size_t threadCountIndex = 0; threadCountIndex < threadCountCount; ++threadCountIndex)
	{
		std::string desc1;

		switch (threadCountIndex)
		{
		case 0:
			desc1 += "1_thread";
			config.ThreadCount = 1;
			config.ThreadsUsingCommonAllocationsProbabilityPercent = 0;
			break;
		case 1:
			desc1 += "16_threads+0%_common";
			config.ThreadCount = 16;
			config.ThreadsUsingCommonAllocationsProbabilityPercent = 0;
			break;
		case 2:
			desc1 += "16_threads+50%_common";
			config.ThreadCount = 16;
			config.ThreadsUsingCommonAllocationsProbabilityPercent = 50;
			break;
		case 3:
			desc1 += "16_threads+100%_common";
			config.ThreadCount = 16;
			config.ThreadsUsingCommonAllocationsProbabilityPercent = 100;
			break;
		case 4:
			desc1 += "2_threads+0%_common";
			config.ThreadCount = 2;
			config.ThreadsUsingCommonAllocationsProbabilityPercent = 0;
			break;
		case 5:
			desc1 += "2_threads+50%_common";
			config.ThreadCount = 2;
			config.ThreadsUsingCommonAllocationsProbabilityPercent = 50;
			break;
		case 6:
			desc1 += "2_threads+100%_common";
			config.ThreadCount = 2;
			config.ThreadsUsingCommonAllocationsProbabilityPercent = 100;
			break;
		default:
			assert(0);
		}

		// 0 = buffers, 1 = images, 2 = buffers and images
		size_t buffersVsImagesCount = 1;
		if (ConfigType >= CONFIG_TYPE_LARGE) ++buffersVsImagesCount;
		for (size_t buffersVsImagesIndex = 0; buffersVsImagesIndex < buffersVsImagesCount; ++buffersVsImagesIndex)
		{
			std::string desc2 = desc1;
			switch (buffersVsImagesIndex)
			{
			case 0: desc2 += ",Buffers"; break;
			case 1: desc2 += ",Images"; break;
			case 2: desc2 += ",Buffers+Images"; break;
			default: assert(0);
			}

			// 0 = small, 1 = large, 2 = small and large
			size_t smallVsLargeCount = 2;
			if (ConfigType >= CONFIG_TYPE_LARGE) ++smallVsLargeCount;
			for (size_t smallVsLargeIndex = 0; smallVsLargeIndex < smallVsLargeCount; ++smallVsLargeIndex)
			{
				std::string desc3 = desc2;
				switch (smallVsLargeIndex)
				{
				case 0: desc3 += ",Smal"; break;
				case 1: desc3 += ",Large"; break;
				case 2: desc3 += ",Small+Large"; break;
				default: assert(0);
				}

				if (smallVsLargeIndex == 1 || smallVsLargeIndex == 2)
					config.MaxBytesToAllocate = 4ull * 1024 * 1024 * 1024; // 4 GB
				else
					config.MaxBytesToAllocate = 4ull * 1024 * 1024;

				// 0 = varying sizes min...max, 1 = set of constant sizes
				size_t constantSizesCount = 1;
				if (ConfigType >= CONFIG_TYPE_SMALL) ++constantSizesCount;
				for (size_t constantSizesIndex = 0; constantSizesIndex < constantSizesCount; ++constantSizesIndex)
				{
					std::string desc4 = desc3;
					switch (constantSizesIndex)
					{
					case 0: desc4 += " Varying_sizes"; break;
					case 1: desc4 += " Constant_sizes"; break;
					default: assert(0);
					}

					config.AllocationSizes.clear();
					// Buffers present
					if (buffersVsImagesIndex == 0 || buffersVsImagesIndex == 2)
					{
						// Small
						if (smallVsLargeIndex == 0 || smallVsLargeIndex == 2)
						{
							// Varying size
							if (constantSizesIndex == 0)
								config.AllocationSizes.push_back({ 4, 16, 1024 });
							// Constant sizes
							else
							{
								config.AllocationSizes.push_back({ 1, 16, 16 });
								config.AllocationSizes.push_back({ 1, 64, 64 });
								config.AllocationSizes.push_back({ 1, 256, 256 });
								config.AllocationSizes.push_back({ 1, 1024, 1024 });
							}
						}
						// Large
						if (smallVsLargeIndex == 1 || smallVsLargeIndex == 2)
						{
							// Varying size
							if (constantSizesIndex == 0)
								config.AllocationSizes.push_back({ 4, 0x10000, 0xA00000 }); // 64 KB ... 10 MB
							// Constant sizes
							else
							{
								config.AllocationSizes.push_back({ 1, 0x10000, 0x10000 });
								config.AllocationSizes.push_back({ 1, 0x80000, 0x80000 });
								config.AllocationSizes.push_back({ 1, 0x200000, 0x200000 });
								config.AllocationSizes.push_back({ 1, 0xA00000, 0xA00000 });
							}
						}
					}
					// Images present
					if (buffersVsImagesIndex == 1 || buffersVsImagesIndex == 2)
					{
						// Small
						if (smallVsLargeIndex == 0 || smallVsLargeIndex == 2)
						{
							// Varying size
							if (constantSizesIndex == 0)
								config.AllocationSizes.push_back({ 4, 0, 0, 4, 32 });
							// Constant sizes
							else
							{
								config.AllocationSizes.push_back({ 1, 0, 0,  4,  4 });
								config.AllocationSizes.push_back({ 1, 0, 0,  8,  8 });
								config.AllocationSizes.push_back({ 1, 0, 0, 16, 16 });
								config.AllocationSizes.push_back({ 1, 0, 0, 32, 32 });
							}
						}
						// Large
						if (smallVsLargeIndex == 1 || smallVsLargeIndex == 2)
						{
							// Varying size
							if (constantSizesIndex == 0)
								config.AllocationSizes.push_back({ 4, 0, 0, 256, 2048 });
							// Constant sizes
							else
							{
								config.AllocationSizes.push_back({ 1, 0, 0,  256,  256 });
								config.AllocationSizes.push_back({ 1, 0, 0,  512,  512 });
								config.AllocationSizes.push_back({ 1, 0, 0, 1024, 1024 });
								config.AllocationSizes.push_back({ 1, 0, 0, 2048, 2048 });
							}
						}
					}

					// 0 = 100%, additional_operations = 0, 1 = 50%, 2 = 5%, 3 = 95% additional_operations = a lot
					size_t beginBytesToAllocateCount = 1;
					if (ConfigType >= CONFIG_TYPE_SMALL) ++beginBytesToAllocateCount;
					if (ConfigType >= CONFIG_TYPE_AVERAGE) ++beginBytesToAllocateCount;
					if (ConfigType >= CONFIG_TYPE_LARGE) ++beginBytesToAllocateCount;
					for (size_t beginBytesToAllocateIndex = 0; beginBytesToAllocateIndex < beginBytesToAllocateCount; ++beginBytesToAllocateIndex)
					{
						std::string desc5 = desc4;

						switch (beginBytesToAllocateIndex)
						{
						case 0:
							desc5 += ",Allocate_100%";
							config.BeginBytesToAllocate = config.MaxBytesToAllocate;
							config.AdditionalOperationCount = 0;
							break;
						case 1:
							desc5 += ",Allocate_50%+Operations";
							config.BeginBytesToAllocate = config.MaxBytesToAllocate * 50 / 100;
							config.AdditionalOperationCount = 1024;
							break;
						case 2:
							desc5 += ",Allocate_5%+Operations";
							config.BeginBytesToAllocate = config.MaxBytesToAllocate * 5 / 100;
							config.AdditionalOperationCount = 1024;
							break;
						case 3:
							desc5 += ",Allocate_95%+Operations";
							config.BeginBytesToAllocate = config.MaxBytesToAllocate * 95 / 100;
							config.AdditionalOperationCount = 1024;
							break;
						default:
							assert(0);
						}

						for (size_t strategyIndex = 0; strategyIndex < strategyCount; ++strategyIndex)
						{
							std::string desc6 = desc5;
							switch (strategyIndex)
							{
							case 0:
								desc6 += ",MinMemory";
								config.AllocationStrategy = VMA_ALLOCATION_CREATE_STRATEGY_MIN_MEMORY_BIT;
								break;
							case 1:
								desc6 += ",MinTime";
								config.AllocationStrategy = VMA_ALLOCATION_CREATE_STRATEGY_MIN_TIME_BIT;
								break;
							default:
								assert(0);
							}

							desc6 += L',';
							desc6 += FREE_ORDER_NAMES[(uint32_t)config.FreeOrder];

							const char* testDescription = desc6.c_str();

							for (size_t repeat = 0; repeat < repeatCount; ++repeat)
							{
								printf("%s #%u\n", testDescription, (uint32_t)repeat);

								Result result{};
								VkResult res = MainTest(result, config);
								TEST(res == VK_SUCCESS);
								if (file)
								{
									WriteMainTestResult(file, CODE_DESCRIPTION, testDescription, config, result);
								}
							}
						}
					}
				}
			}
		}
	}
}

static void PerformCustomMainTest(FILE* file)
{
	Config config{};
	config.RandSeed = 65735476;
	//config.MaxBytesToAllocate = 4ull * 1024 * 1024; // 4 MB
	config.MaxBytesToAllocate = 4ull * 1024 * 1024 * 1024; // 4 GB
	config.MemUsageProbability[0] = 1; // VMA_MEMORY_USAGE_GPU_ONLY
	config.FreeOrder = FREE_ORDER::FORWARD;
	config.ThreadCount = 16;
	config.ThreadsUsingCommonAllocationsProbabilityPercent = 50;
	config.AllocationStrategy = 0;

	// Buffers
	//config.AllocationSizes.push_back({4, 16, 1024});
	config.AllocationSizes.push_back({ 4, 0x10000, 0xA00000 }); // 64 KB ... 10 MB

	// Images
	//config.AllocationSizes.push_back({4, 0, 0, 4, 32});
	//config.AllocationSizes.push_back({4, 0, 0, 256, 2048});

	config.BeginBytesToAllocate = config.MaxBytesToAllocate * 5 / 100;
	config.AdditionalOperationCount = 1024;

	Result result{};
	VkResult res = MainTest(result, config);
	TEST(res == VK_SUCCESS);
	WriteMainTestResult(file, "Foo", "CustomTest", config, result);
}


void TestDmm(void)
{

	//测试1，单线程申请、释放
	{
		std::random_device rd;
		std::vector<void*> vecPtr;
		for (int i = 0; i < 100; i++)
		{
			size_t len = rd() % (10 << 20) + 1;
			void* pmem = dmm::dmmAlloc(len);
			*(char*)pmem = 'B';
			*((char*)pmem + len - 1) = 'E';
			vecPtr.push_back(pmem);
		}

		std::random_shuffle(vecPtr.begin(), vecPtr.end());
		for (auto e : vecPtr)
		{
			dmm::dmmFree(e);
		}
		std::cout << "==============================================" << std::endl;
		std::cout << dmm::dmmGetMemUsageInfo() << std::endl;
		std::wcout<< "dmm test 1 end." << std::endl;
	}

	//测试2，多线程申请、释放，A线程申请A线程释放
	{
		constexpr int threadCnt = 8;
		std::thread t[threadCnt];
		bool bRunning = true;
		for (int i = 0; i < threadCnt; i++)
		{
			t[i] = std::thread([&bRunning]() {
				while (bRunning)
				{
					std::random_device rd;
					std::vector<void*> vecPtr;

					for (int i = 0; i < 100; i++)
					{
						size_t len = rd() % (10 << 20) + 1;
						void* pmem = dmm::dmmAlloc(len);
						*(char*)pmem = 'B';
						*((char*)pmem + len - 1) = 'E';
						vecPtr.push_back(pmem);
					}

					std::random_shuffle(vecPtr.begin(), vecPtr.end());
					for (auto e : vecPtr)
					{
						dmm::dmmFree(e);
					}
				}
			});
		}

		std::this_thread::sleep_for(std::chrono::seconds(10));
		bRunning = false;
		for (int i = 0; i < threadCnt; i++)
		{
			t[i].join();
		}
		std::wcout<< "dmm test 2 end." << std::endl;
	}


	//测试3，多线程申请、释放，A线程申请、B线程释放
	{
		constexpr int threadCnt = 4;
		constexpr int MAX_NUM = 2500;
		std::thread tAlloc[threadCnt];
		std::thread tFree[threadCnt];
		bool bRunning = true;

		std::mutex mtx;
		std::list<void*> listPtr;

		for (int i = 0; i < threadCnt; i++)
		{
			tAlloc[i] = std::thread([&mtx, &listPtr, &bRunning, &MAX_NUM]() {
				std::random_device rd;
				while (bRunning)
				{
					if (listPtr.size() < MAX_NUM)
					{
						size_t len = rd() % (10 << 20) + 1;
						void* pmem = dmm::dmmAlloc(len);
						*(char*)pmem = 'B';
						*((char*)pmem + len - 1) = 'E';

						std::unique_lock<std::mutex> lk(mtx);
						listPtr.push_back(pmem);
					}
				}
			});

			tFree[i] = std::thread([&mtx, &listPtr, &bRunning]() {
				while (bRunning)
				{
					std::unique_lock<std::mutex> lk(mtx);
					if (listPtr.size() > 0)
					{
						void* ptr = listPtr.front();
						listPtr.pop_front();
						dmm::dmmFree(ptr);
					}
				}
			});
		}

		std::this_thread::sleep_for(std::chrono::seconds(10));
		bRunning = false;
		for (int i = 0; i < threadCnt; i++)
		{
			tAlloc[i].join();
		}
		for (int i = 0; i < threadCnt; i++)
		{
			tFree[i].join();
		}

		for (auto e : listPtr)
		{
			dmm::dmmFree(e);
		}
		std::wcout<< "dmm test 3 end." << std::endl;
	}

}

int main(void)
{
	dmm::dmmInit();

	printf("TESTING:\n");


	if (false)
	{
		////////////////////////////////////////////////////////////////////////////////
		// Temporarily insert custom tests here:
		return 0;
	}

	// # Simple tests
	TestJson();
	TestBasics();
	TestVirtualBlocks();
	TestVirtualBlocksAlgorithms();
	TestVirtualBlocksAlgorithmsBenchmark();
	TestAllocationVersusResourceSize();
	TestPool_SameSize();
	TestPool_MinBlockCount();
	TestPool_MinAllocationAlignment();
	TestPoolsAndAllocationParameters();
	TestHeapSizeLimit();
	TestBudget();
	TestMapping();
	TestMappingHysteresis();
	TestDeviceLocalMapped();
	TestMappingMultithreaded();
	TestLinearAllocator();
	ManuallyTestLinearAllocator();
	TestLinearAllocatorMultiBlock();
	TestAllocationAlgorithmsCorrectness();

	BasicTestTLSF();
	BasicTestAllocatePages();

	TestMemoryPriority();

	{
		FILE* file = fopen("Algorithms.csv", "w");
		assert(file != NULL);
		BenchmarkAlgorithms(file);
		fclose(file);
	}

	TestDefragmentationVsMapping();

	// # Detailed tests
	FILE* file = fopen("Results.csv", "w");
	assert(file != NULL);
	WriteMainTestResultHeader(file);
	PerformMainTests(file);
	PerformCustomMainTest(file);
	fclose(file);

	TestDmm();

	printf("Done, all PASSED.\n");

	dmm::dmmDeinit();

	return 0;
}